<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            LeetCode链表 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">LeetCode链表</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2019-02-27 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E9%93%BE%E8%A1%A8/">链表</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>17.1k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>77 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <blockquote>
<p>链表专题是最开始学算法的时候写的，很多代码都写得很烂，目前正在慢慢的重写，u1s1链表的题还是很考验细心的，稍不注意就连错了</p>
</blockquote>
<h2 id="2-两数相加"><a href="#2-两数相加" class="headerlink" title="2. 两数相加"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/add-two-numbers" >2. 两数相加<i class="fas fa-external-link-alt"></i></a></h2><p>给出两个 <strong>非空</strong> 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 <strong>逆序</strong> 的方式存储的，并且它们的每个节点只能存储 <strong>一位</strong> 数字。<br> 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。<br>您可以假设除了数字 0 之外，这两个数都不会以 0 开头。</p>
<p>输入：(2 -&gt; 4 -&gt; 3) + (5 -&gt; 6 -&gt; 4)</p>
<p>输出：7 -&gt; 0 -&gt; 8</p>
<p>原因：342 + 465 = 807</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//比较推荐的写法，简洁一点，在lc上提交区别不大</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">addTwoNumbers</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    ListNode temp=dummyNode;</span><br><span class="line">    dummyNode.next=temp;</span><br><span class="line">    <span class="keyword">int</span> carry=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(l1!=<span class="keyword">null</span> || l2!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">int</span> sum= (l1!=<span class="keyword">null</span>?l1.val:<span class="number">0</span>) + (l2!=<span class="keyword">null</span>?l2.val:<span class="number">0</span>)+ carry;</span><br><span class="line">        temp.next=<span class="keyword">new</span> ListNode(sum%<span class="number">10</span>);</span><br><span class="line">        temp=temp.next;</span><br><span class="line">        carry=sum/<span class="number">10</span>;</span><br><span class="line">        l1=l1!=<span class="keyword">null</span>?l1.next:<span class="keyword">null</span>;</span><br><span class="line">        l2=l2!=<span class="keyword">null</span>?l2.next:<span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(carry!=<span class="number">0</span>) temp.next=<span class="keyword">new</span> ListNode(<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><del>很久之前写的代码了，代码很乱，用0补齐短的那个然后对应相加注意进位就行了</del></p>
<p>2020.3.22 把之前的代码删了，一年前的代码，写的太丑了</p>
<p><strong>解法二</strong></p>
<p>2020.3.22 新增了一个解法，有点偏，没啥意思，不过熟悉下链表还是可以</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//这个解法有点偏了,为了不new节点直接在原链表上修改的</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">addTwoNumbers</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=l1;</span><br><span class="line">    <span class="keyword">int</span> carry=<span class="number">0</span>;</span><br><span class="line">    ListNode last=l1;</span><br><span class="line">    <span class="keyword">while</span>(l1!=<span class="keyword">null</span> &amp;&amp; l2!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">int</span> sum= l1.val + l2.val+ carry;</span><br><span class="line">        l1.val=sum%<span class="number">10</span>;</span><br><span class="line">        carry=sum/<span class="number">10</span>;</span><br><span class="line">        last=l1;</span><br><span class="line">        l1=l1.next;</span><br><span class="line">        l2=l2.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(l1!=<span class="keyword">null</span> &amp;&amp; carry!=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">int</span> sum = l1.val + carry;</span><br><span class="line">        l1.val=sum%<span class="number">10</span>;</span><br><span class="line">        carry=sum/<span class="number">10</span>;</span><br><span class="line">        last=l1;</span><br><span class="line">        l1=l1.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(l2!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        last.next=l2;</span><br><span class="line">        <span class="keyword">while</span>(l2!=<span class="keyword">null</span> &amp;&amp; carry!=<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">int</span> sum = l2.val + carry;</span><br><span class="line">            l2.val=sum%<span class="number">10</span>;</span><br><span class="line">            carry=sum/<span class="number">10</span>;</span><br><span class="line">            last=l2;</span><br><span class="line">            l2=l2.next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(carry!=<span class="number">0</span>) last.next=<span class="keyword">new</span> ListNode(<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="445-两数相加Ⅱ"><a href="#445-两数相加Ⅱ" class="headerlink" title="445. 两数相加Ⅱ"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/add-two-numbers-ii" >445. 两数相加Ⅱ<i class="fas fa-external-link-alt"></i></a></h2><p>给定两个<strong>非空</strong>链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。<br>你可以假设除了数字 0 之外，这两个数字都不会以零开头。</p>
<p>进阶:<br>如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。</p>
<p>输入: (7 -&gt; 2 -&gt; 4 -&gt; 3) + (5 -&gt; 6 -&gt; 4)</p>
<p>输出: 7 -&gt; 8 -&gt; 0 -&gt; 7</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">addTwoNumbers</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    BigInteger b1 = <span class="keyword">new</span> BigInteger(list2num(l1));</span><br><span class="line">    BigInteger b2 = <span class="keyword">new</span> BigInteger(list2num(l2));</span><br><span class="line">    String resStr=b1.add(b2).toString();</span><br><span class="line">    <span class="comment">//再变成字符串存到连表里面</span></span><br><span class="line">    ListNode res=<span class="keyword">new</span> ListNode(<span class="number">1</span>);</span><br><span class="line">    ListNode real=res;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;resStr.length();i++) &#123;</span><br><span class="line">        real.next=<span class="keyword">new</span> ListNode(Integer.valueOf(resStr.charAt(i)-<span class="number">48</span>));</span><br><span class="line">        real=real.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.next;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> String  <span class="title">list2num</span><span class="params">(ListNode l)</span></span>&#123;</span><br><span class="line">    String num=<span class="string">&quot;&quot;</span>;</span><br><span class="line">    <span class="keyword">while</span>(l!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        num=num+l.val;</span><br><span class="line">        l=l.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> num;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这两题方法很多，下面那题实际上是上面那一题反过来的，但是题目要求不改变链表所以可以利用栈来反转，然后就跟上面的类似了，然后这里我偷了个懒用的<code>BigInteger</code>搞的速度也还行 77%beat。</p>
<p><strong>解法二</strong></p>
<p>（update: 2020.4.14）上面的解法笔试这样写倒是无所谓，面试这样写肯定是不行的，咱还是得规规矩矩的写</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span>  ListNode <span class="title">addTwoNumbers</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//用数组的话不知道有多长,需要多遍历两遍</span></span><br><span class="line">    Deque&lt;Integer&gt; stack1=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    Deque&lt;Integer&gt; stack2=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    ListNode res=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">while</span>(l1!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        stack1.push(l1.val);</span><br><span class="line">        l1=l1.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(l2!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        stack2.push(l2.val);</span><br><span class="line">        l2=l2.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> carry=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(!stack1.isEmpty() || !stack2.isEmpty() || carry&gt;<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">int</span> temp=(stack1.isEmpty()?<span class="number">0</span>:stack1.pop())+(stack2.isEmpty()?<span class="number">0</span>:stack2.pop())+carry;</span><br><span class="line">        <span class="comment">//头插法</span></span><br><span class="line">        ListNode next=res.next;</span><br><span class="line">        ListNode newNode=<span class="keyword">new</span> ListNode(temp%<span class="number">10</span>);</span><br><span class="line">        res.next=newNode;</span><br><span class="line">        newNode.next=next;</span><br><span class="line">        carry=temp/<span class="number">10</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>最后的头插法还是挺好的，我开始还想着翻转一下的，我看见评论区有人用递归写，我试了下，还是算了，太麻烦了，还没上面的简洁，写一大坨初始化，然后再递归，代码一点都不简洁，没啥意义</p>
<h2 id="876-链表的中间节点"><a href="#876-链表的中间节点" class="headerlink" title="876. 链表的中间节点"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/middle-of-the-linked-list" >876. 链表的中间节点<i class="fas fa-external-link-alt"></i></a></h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">middleNode</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">        ListNode fast=head;</span><br><span class="line">        ListNode slow=head;</span><br><span class="line">        <span class="comment">// 1 2 3 4 5 6 7</span></span><br><span class="line">        <span class="keyword">while</span>(fast!=<span class="keyword">null</span>&amp;&amp;fast.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            fast=fast.next.next;</span><br><span class="line">            slow=slow.next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> slow;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p><code>快慢指针</code>，很常见很经典的做法后面很多题会用到这个。</p>
</blockquote>
<h2 id="206-反转链表"><a href="#206-反转链表" class="headerlink" title="206. 反转链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-linked-list" >206. 反转链表<i class="fas fa-external-link-alt"></i></a></h2><p>反转一个单链表。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">reverseList</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="keyword">null</span> || head.next == <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> head;</span><br><span class="line">    &#125;</span><br><span class="line">    ListNode newHead = reverseList(head.next);</span><br><span class="line">    <span class="comment">//从后往前</span></span><br><span class="line">    head.next.next = head;</span><br><span class="line">    head.next = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">return</span> newHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//三指针迭代</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">reverseList2</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    ListNode pre=head;</span><br><span class="line">    ListNode cur=head.next;</span><br><span class="line">    ListNode temp;</span><br><span class="line">    <span class="keyword">while</span>(cur!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        temp=cur.next;</span><br><span class="line">        cur.next=pre;</span><br><span class="line">        pre=cur;</span><br><span class="line">        cur=temp;</span><br><span class="line">    &#125;</span><br><span class="line">    head.next=<span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">return</span> pre;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="92-反转链表Ⅱ"><a href="#92-反转链表Ⅱ" class="headerlink" title="92. 反转链表Ⅱ"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-linked-list-ii" >92. 反转链表Ⅱ<i class="fas fa-external-link-alt"></i></a></h2><p>反转从位置 <em>m</em> 到 <em>n</em> 的链表。请使用一趟扫描完成反转。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">reverseBetween</span><span class="params">(ListNode head, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(m==n) <span class="keyword">return</span> head;</span><br><span class="line">    <span class="comment">//用来遍历</span></span><br><span class="line">    ListNode pre=head;</span><br><span class="line">    ListNode mid=head.next;</span><br><span class="line">    ListNode rear=<span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//在遍历的中间连接这个表 时间复杂厚度O(N)</span></span><br><span class="line">    <span class="comment">//所以需要先保存 m前的节点用于后面到n的时候连接n和前面的部分 preM</span></span><br><span class="line">    <span class="comment">//还要保存m节点，在后面遍历到n的时候将M节点和后面的部分连接</span></span><br><span class="line">    <span class="comment">//中间段的前后节点 </span></span><br><span class="line">    ListNode preM =<span class="keyword">null</span>;</span><br><span class="line">    ListNode valM=head;</span><br><span class="line">    <span class="comment">//ListNode nNext=null;</span></span><br><span class="line">    <span class="keyword">int</span> count =<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(count &lt;=n-<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="comment">//count的位置实际上是指的pre的位置因为只有pre是从head开始走的</span></span><br><span class="line">        <span class="comment">//尾指针后移</span></span><br><span class="line">        rear=mid.next;</span><br><span class="line">        <span class="keyword">if</span>(count==m-<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">//保存M点前面的节点和M节点</span></span><br><span class="line">            preM=pre;</span><br><span class="line">            valM=mid;</span><br><span class="line">            <span class="comment">//System.out.println(&quot;preM :&quot;+preM.val);</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(count==n-<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">//连接n后面节点的值</span></span><br><span class="line">            valM.next=rear;</span><br><span class="line">            <span class="comment">//在这里判断下m前有没有元素</span></span><br><span class="line">            <span class="keyword">if</span>(m==<span class="number">1</span>)&#123;</span><br><span class="line">                head=mid;</span><br><span class="line">            &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">                preM.next=mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(count &gt;= m &amp;&amp; count &lt;=n-<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">//只有mid的位置大于m小于等于n才会将节点next域反转</span></span><br><span class="line">            mid.next=pre;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//其他两个指针也向后移动</span></span><br><span class="line">        pre=mid;</span><br><span class="line">        mid=rear;</span><br><span class="line">        count++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>代码写的比较烂但是思路还是比较清晰，只扫描了一遍链表 2ms beat 100%，但是创建的指针有点多，抠边界要细心。</p>
<p><strong>解法二</strong></p>
<p>被本来是像把上面的解法删掉的，想了一下还是留着，提醒下自己，上面的解法不够通用，属于一次性的解法，细节也很多，当初可能是追求在一个循环内写完，所以可能写的比较难看</p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">reverseBetween2</span><span class="params">(head *ListNode, m <span class="keyword">int</span>, n <span class="keyword">int</span>)</span> *<span class="title">ListNode</span></span> &#123;</span><br><span class="line">    dummyNode := &amp;ListNode&#123;</span><br><span class="line">        Val:  <span class="number">-1</span>,</span><br><span class="line">        Next: head,</span><br><span class="line">    &#125;</span><br><span class="line">    mpre := dummyNode <span class="comment">//m节点前的节点</span></span><br><span class="line">    <span class="keyword">for</span> i := m; i &gt; <span class="number">1</span>; i-- &#123;</span><br><span class="line">        mpre = mpre.Next</span><br><span class="line">    &#125;</span><br><span class="line">    pre := mpre</span><br><span class="line">    cur := mpre.Next</span><br><span class="line">    <span class="comment">//  2   4</span></span><br><span class="line">    <span class="comment">//1 2 3 4 5</span></span><br><span class="line">    <span class="keyword">for</span> i := m; i &lt;= n; i++ &#123;</span><br><span class="line">        next := cur.Next</span><br><span class="line">        cur.Next = pre</span><br><span class="line">        pre = cur</span><br><span class="line">        cur = next</span><br><span class="line">    &#125;</span><br><span class="line">    mpre.Next.Next = cur <span class="comment">//2.next=5</span></span><br><span class="line">    mpre.Next = pre      <span class="comment">//1.next=4</span></span><br><span class="line">    <span class="keyword">return</span> dummyNode.Next</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这个解法实际上就是普通一个翻转，然后处理翻转部分的头尾节点连接，但是代码比上面的简洁多了</p>
<p><strong>解法三</strong></p>
<p>头插法的应用，将翻转部分节点用头插法插入pre后，也挺不错</p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="comment">//头插法</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">reverseBetween</span><span class="params">(head *ListNode, m <span class="keyword">int</span>, n <span class="keyword">int</span>)</span> *<span class="title">ListNode</span></span> &#123;</span><br><span class="line">    dummyNode := &amp;ListNode&#123;</span><br><span class="line">        Val:  <span class="number">-1</span>,</span><br><span class="line">        Next: head,</span><br><span class="line">    &#125;</span><br><span class="line">    mpre := dummyNode <span class="comment">//m节点前的节点</span></span><br><span class="line">    <span class="keyword">for</span> i := m; i &gt; <span class="number">1</span>; i-- &#123;</span><br><span class="line">        mpre = mpre.Next</span><br><span class="line">    &#125;</span><br><span class="line">    cur := mpre.Next</span><br><span class="line">    <span class="comment">//1 |2 3 4| 5</span></span><br><span class="line">    <span class="keyword">for</span> i := m; i &lt; n; i++ &#123;</span><br><span class="line">        <span class="comment">//除非m=n=len不然next肯定不为空,但是这种情况已经被循环的条件过滤了</span></span><br><span class="line">        next := cur.Next</span><br><span class="line">        cur.Next = next.Next</span><br><span class="line">        next.Next = mpre.Next</span><br><span class="line">        mpre.Next = next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.Next</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="725-分隔链表"><a href="#725-分隔链表" class="headerlink" title="725. 分隔链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/split-linked-list-in-parts/" >725. 分隔链表<i class="fas fa-external-link-alt"></i></a></h2><p>Given a (singly) linked list with head node <code>root</code>, write a function to split the linked list into <code>k</code> consecutive linked list “parts”.</p>
<p>The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.</p>
<p>The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.</p>
<p>Return a List of ListNode’s representing the linked list parts that are formed.</p>
<p>Examples 1-&gt;2-&gt;3-&gt;4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]</p>
<p><strong>Example 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: </span><br><span class="line">root = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>], k = <span class="number">5</span></span><br><span class="line">Output: [[<span class="number">1</span>],[<span class="number">2</span>],[<span class="number">3</span>],[],[]]</span><br><span class="line">Explanation:</span><br><span class="line">The input and each element of the output are ListNodes, not arrays.</span><br><span class="line">For example, the input root has root.val = <span class="number">1</span>, root.next.val = <span class="number">2</span>, \root.next.next.val = <span class="number">3</span>, and root.next.next.next = <span class="keyword">null</span>.</span><br><span class="line">The first element output[<span class="number">0</span>] has output[<span class="number">0</span>].val = <span class="number">1</span>, output[<span class="number">0</span>].next = <span class="keyword">null</span>.</span><br><span class="line">The last element output[<span class="number">4</span>] is <span class="keyword">null</span>, but it<span class="string">&#x27;s string representation as a ListNode is [].</span></span><br></pre></td></tr></table></figure>

<p><strong>Example 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Input: </span><br><span class="line">root = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">9</span>, <span class="number">10</span>], k = <span class="number">3</span></span><br><span class="line">Output: [[<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>], [<span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>], [<span class="number">8</span>, <span class="number">9</span>, <span class="number">10</span>]]</span><br><span class="line">Explanation:</span><br><span class="line">The input has been split into consecutive parts with size difference at most <span class="number">1</span>, and earlier parts are a larger size than the later parts.</span><br></pre></td></tr></table></figure>

<p><strong>Note:</strong></p>
<p>The length of <code>root</code> will be in the range <code>[0, 1000]</code>.</p>
<p>Each value of a node in the input will be an integer in the range <code>[0, 999]</code>.</p>
<p><code>k</code> will be an integer in the range <code>[1, 50]</code>.</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> ListNode[] splitListToParts(ListNode root, <span class="keyword">int</span> k) &#123;</span><br><span class="line">    <span class="comment">//先要获取下链表的长度</span></span><br><span class="line">    ListNode temp=root;</span><br><span class="line">    ListNode next=root;</span><br><span class="line">    ListNode [] result=<span class="keyword">new</span> ListNode[k];</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">        count++;</span><br><span class="line">    &#125;</span><br><span class="line">    temp=root;</span><br><span class="line">    <span class="comment">//任意两部分差距不能大于1，大的在前，小的在后面</span></span><br><span class="line">    <span class="comment">//其实就是对count进行分配</span></span><br><span class="line">    <span class="comment">//注意: 有null的情况一定是 k&gt;count 直接按 1 切分就完事了</span></span><br><span class="line">    <span class="comment">//k&lt;count的情况只要在 count/k 的前几个元素上加上 count/k 的余数就行了</span></span><br><span class="line">    <span class="keyword">int</span> size=count/k;</span><br><span class="line">    <span class="keyword">int</span> num=count%k;</span><br><span class="line">    result[<span class="number">0</span>]=root;</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(k&lt;=count)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;temp!=<span class="keyword">null</span> &amp;&amp; index &lt; k;i++)&#123;</span><br><span class="line">            next=temp.next;</span><br><span class="line">            <span class="keyword">if</span>(i&lt;=(size+<span class="number">1</span>)*num &amp;&amp; i%(size+<span class="number">1</span>)==<span class="number">0</span>)&#123;</span><br><span class="line">                <span class="comment">//前几个res的分割点</span></span><br><span class="line">                result[index++]=next;</span><br><span class="line">                <span class="comment">//切断</span></span><br><span class="line">                temp.next=<span class="keyword">null</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span>(i&gt;(size+<span class="number">1</span>)*num &amp;&amp; (i-num)%size==<span class="number">0</span>)&#123;</span><br><span class="line">                result[index++]=next;</span><br><span class="line">                temp.next=<span class="keyword">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            temp=next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="comment">//剩下的情况就是后面要补null的情况</span></span><br><span class="line">        <span class="comment">// 这里两种情况应该是可以合并的，但是k&gt;count num&gt;0 懒得去抠边界</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;k;i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(temp==<span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="comment">//这个if其实没必要</span></span><br><span class="line">                result[i]=<span class="keyword">null</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">                next=temp.next;</span><br><span class="line">                result[i]=next;</span><br><span class="line">                temp.next=<span class="keyword">null</span>;</span><br><span class="line">                temp=next;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>3ms beat 89% 这题也比较简单主要是边界要抠好</p>
<h2 id="86-分隔-割-链表"><a href="#86-分隔-割-链表" class="headerlink" title="86. 分隔(割)链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/partition-list" >86. 分隔(割)链表<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表和一个特定值<code>x</code>，对链表进行分隔，使得所有小于<code>x</code>的节点都在大于或等于<code>x</code>的节点之前。</p>
<p>你应当保留两个分区中每个节点的初始相对位置。</p>
<p><strong>输入:</strong> head = 1-&gt;4-&gt;3-&gt;2-&gt;5-&gt;2, <em>x</em> = 3</p>
<p><strong>输出:</strong> 1-&gt;2-&gt;2-&gt;4-&gt;3-&gt;5</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">partition</span><span class="params">(ListNode head, <span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//先在头部加一个dummy节点统一操作</span></span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    <span class="comment">//分割点</span></span><br><span class="line">    ListNode pre=cutNode=dummyNode;</span><br><span class="line">    ListNode cur=head;</span><br><span class="line">    <span class="keyword">int</span> cut=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(cur!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(cur.val&gt;=x&amp;&amp;cut==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="comment">//只会执行一次在找到第一个val&gt;=x的节点的时候---保存分割点</span></span><br><span class="line">            cutNode=pre;</span><br><span class="line">            cut=<span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span>(cur.val&lt;x &amp;&amp; cut==<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">//找到分割点后 遍历到val&lt;x的节点的情况---将cur连接到cutNode的后面 处理好cur相邻的两个节点</span></span><br><span class="line">            <span class="comment">//先处理好cur相邻的节点</span></span><br><span class="line">            pre.next=cur.next;</span><br><span class="line">            <span class="comment">//连接cutNode</span></span><br><span class="line">            cur.next=cutNode.next;</span><br><span class="line">            cutNode.next=cur;</span><br><span class="line">            <span class="comment">//cutNode后移</span></span><br><span class="line">            cutNode=cur;</span><br><span class="line">        &#125;</span><br><span class="line">        pre=cur;</span><br><span class="line">        cur=cur.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题也挺简单和上面的那题名字一样是在整理这篇博客的时候现场做的(2019.2.27)前后大概半个小时orz。。。比较菜，但是这个我没有在本地跑直接在LeetCode上提交的然后就过了 1ms beat84% 感觉思路比较清晰就没有本地跑，提交记录上最快的居然是用了额外空间new了两个链表然后连起来的。。。醉了可能是测试用例太少了。</p>
<h2 id="160-相交链表"><a href="#160-相交链表" class="headerlink" title="160. 相交链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/intersection-of-two-linked-lists" >160. 相交链表<i class="fas fa-external-link-alt"></i></a></h2><p>编写一个程序，找到两个单链表相交的起始节点。<br>如下面的两个链表：<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/NVEXndTcF1R6.png?imageslim"
                      alt="mark"
                ></p>
<p>在节点 c1 开始相交。</p>
<p><strong>示例 1：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/ymln2djUVieT.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>输入</strong>: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3<br><strong>输出</strong>: Reference of the node with value = 8<br><strong>输入解释</strong>:相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。</p>
<p><strong>示例 2：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/2F7qqhkUIWog.png?imageslim"
                      alt="mark"
                ><br><strong>输入</strong>:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1<br><strong>输出</strong>:Reference of the node with value = 2<br><strong>输入解释</strong>:相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。</p>
<p><strong>示例 3：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/hKSAelGSE1TY.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>输入</strong>:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2<br><strong>输出</strong>:null<br><strong>输入解释</strong>:从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。<br><strong>解释</strong>:这两个链表不相交，因此返回 null。</p>
<p><strong>注意：</strong></p>
<ul>
<li>  如果两个链表没有交点，返回 <code>null</code>.</li>
<li>  在返回结果后，两个链表仍须保持原有的结构。</li>
<li>  可假定整个链表结构中没有循环。</li>
<li>  程序尽量满足 O(<em>n</em>) 时间复杂度，且仅用 O(<em>1</em>) 内存。</li>
</ul>
<p><strong>解法一：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">getIntersectionNode</span><span class="params">(ListNode headA, ListNode headB)</span> </span>&#123;</span><br><span class="line">    ListNode pA=headA;</span><br><span class="line">    ListNode pB=headB;</span><br><span class="line">    <span class="comment">//计算两个链表长度然后计算差距然后向后对齐</span></span><br><span class="line">    <span class="keyword">int</span> lenA=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> lenB=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(pA!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        pA=pA.next;</span><br><span class="line">        lenA++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(pB!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        pB=pB.next;</span><br><span class="line">        lenB++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> dis=lenB&gt;lenA?lenB-lenA:lenA-lenB;</span><br><span class="line">    <span class="keyword">if</span>(lenB&gt;lenA)&#123;</span><br><span class="line">        <span class="keyword">while</span>(dis--&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            headB=headB.next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">while</span>(dis--&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            headA=headA.next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//不相等就一直向后移</span></span><br><span class="line">    <span class="keyword">while</span>(headA!=headB)&#123;</span><br><span class="line">        <span class="comment">//如果有一条为空说明没有交点</span></span><br><span class="line">        <span class="keyword">if</span>(headA.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        headA=headA.next;</span><br><span class="line">        headB=headB.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> headA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这种方法比较直接直接计算两个链表的长度然后计算差值然后将长的那个移动到对应的位置让<code>两条链表尾对齐</code>然后一起向后移动<br><strong>解法二：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//方法二 </span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">getIntersectionNode2</span><span class="params">(ListNode headA, ListNode headB)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//当一个指针到结尾时转到另一个链表头再向后移动 ，这样做的目的和就是可以直接消除链表之间的长度差，向后对齐，方法还是很巧妙的。</span></span><br><span class="line">    ListNode pA=headA;</span><br><span class="line">    ListNode pB=headB;</span><br><span class="line">    <span class="keyword">if</span>(headB==<span class="keyword">null</span> || headA==<span class="keyword">null</span>)</span><br><span class="line">                 <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//while(pA!=null &amp;&amp; pB!=null )&#123;</span></span><br><span class="line">    <span class="keyword">while</span>(pA!=pB)&#123;</span><br><span class="line">        <span class="comment">//要保证两个==null的时候都只能执行一次不然如果没有交点就会死循环</span></span><br><span class="line">        <span class="comment">//改变while的条件</span></span><br><span class="line">        <span class="comment">//改变pA，pB跳转的条件</span></span><br><span class="line">        <span class="comment">//这样就可以保证最后没交点的时候 第二遍循环pA和pB最后会同时等于null会有出口不会死循环</span></span><br><span class="line">        pA=pA==<span class="keyword">null</span>?headB:pA.next;</span><br><span class="line">        pB=pB==<span class="keyword">null</span>?headA:pB.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p> 同时遍历两个链表，当一个指针到结尾时转到另一个链表头再向后移动 ，这样做的目的和就是可以直接消除链表之间的长度差，使之尾对齐，方法还是很巧妙的，代码也比较简洁。</p>
</blockquote>
<h2 id="234-回文链表"><a href="#234-回文链表" class="headerlink" title="234. 回文链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/palindrome-linked-list" >234. 回文链表<i class="fas fa-external-link-alt"></i></a></h2><p>请判断一个链表是否为回文链表。</p>
<p><strong>示例 1:</strong></p>
<p><strong>输入:</strong> 1-&gt;2<br><strong>输出:</strong> false</p>
<p><strong>示例 2:</strong></p>
<p><strong>输入:</strong> 1-&gt;2-&gt;2-&gt;1<br><strong>输出:</strong> true</p>
<p><strong>进阶：</strong><br>你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isPalindrome</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span> || head.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 利用快慢指针找到中点</span></span><br><span class="line">    ListNode fast = head;</span><br><span class="line">    ListNode slow = head;</span><br><span class="line">    <span class="keyword">while</span> (fast.next != <span class="keyword">null</span>) &#123;</span><br><span class="line">        fast = fast.next.next == <span class="keyword">null</span> ? fast.next : fast.next.next;</span><br><span class="line">        slow = slow.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果是偶数节点，slow就是偏右的那个 奇数就是正中间的 奇数在正中间不用管</span></span><br><span class="line">    <span class="comment">// fast是尾节点 1 1 1 1 1 1</span></span><br><span class="line">    resverList(slow);</span><br><span class="line">    <span class="comment">//slow.next==null</span></span><br><span class="line">    <span class="comment">// check</span></span><br><span class="line">    <span class="keyword">while</span> (fast != <span class="keyword">null</span> &amp;&amp; head != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (fast.val != head.val) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        fast = fast.next;</span><br><span class="line">        head = head.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">resverList</span><span class="params">(ListNode node)</span> </span>&#123;</span><br><span class="line">    ListNode cur = node;</span><br><span class="line">    ListNode pre = <span class="keyword">null</span>;</span><br><span class="line">    ListNode next = node;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="keyword">null</span>) &#123;</span><br><span class="line">        next = next.next;</span><br><span class="line">        cur.next = pre;</span><br><span class="line">        pre = cur;</span><br><span class="line">        cur = next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题就用到了上面的翻转链表的方法，不过这里只翻转了一半，翻转了后半段然后从两边到中间逐个节点对比</p>
<h2 id="237-删除链表中的节点"><a href="#237-删除链表中的节点" class="headerlink" title="237. 删除链表中的节点"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/delete-node-in-a-linked-list" >237. 删除链表中的节点<i class="fas fa-external-link-alt"></i></a></h2><p>请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。</p>
<p>现有一个链表 – head = [4,5,1,9]，它可以表示为:</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/9MUvMzlcAN0G.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>示例 1:</strong></p>
<p><strong>输入:</strong> head = [4,5,1,9], node = 5<br><strong>输出:</strong> [4,1,9]<br><strong>解释:</strong> 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -&gt; 1 -&gt; 9.</p>
<p><strong>示例 2:</strong></p>
<p><strong>输入:</strong> head = [4,5,1,9], node = 1<br><strong>输出:</strong> [4,5,9]<br><strong>解释:</strong> 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -&gt; 5 -&gt; 9.</p>
<p><strong>说明:</strong></p>
<ul>
<li>  链表至少包含两个节点。</li>
<li>  链表中所有节点的值都是唯一的。</li>
<li>  给定的节点为非末尾节点并且一定是链表中的一个有效节点。</li>
<li>  不要从你的函数中返回任何结果。</li>
</ul>
<p><strong>二货做法</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span>  <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">deleteNodelow</span><span class="params">(ListNode node)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//思路就是和node后面的元素一直交换，就像冒泡排序一样</span></span><br><span class="line">    ListNode next;</span><br><span class="line">    ListNode temp=<span class="keyword">new</span> ListNode(<span class="number">0</span>);</span><br><span class="line">    ListNode pre=temp;</span><br><span class="line">    <span class="keyword">while</span>(node.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        next=node.next;</span><br><span class="line">        <span class="keyword">if</span>(node.next.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            pre=node;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//先保存最后一个节点前的节点</span></span><br><span class="line">        <span class="comment">//交换当前节点和后一个节点</span></span><br><span class="line">        temp.val=node.val;</span><br><span class="line">        node.val=next.val;</span><br><span class="line">        next.val=temp.val;</span><br><span class="line">        node=next;</span><br><span class="line">    &#125;</span><br><span class="line">    pre.next=<span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>首先想到的愚蠢的做法,怎么这么蠢？？？？</p>
<p><strong>正确做法</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span>  <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">deleteNode</span><span class="params">(ListNode node)</span> </span>&#123;</span><br><span class="line">      node.val=node.next.val;</span><br><span class="line">      node.next=node.next.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="203-移除链表元素"><a href="#203-移除链表元素" class="headerlink" title="203. 移除链表元素"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-linked-list-elements" >203. 移除链表元素<i class="fas fa-external-link-alt"></i></a></h2><p>删除链表中等于给定值 val 的所有节点。</p>
<p><strong>示例:</strong></p>
<p><strong>输入:</strong> 1-&gt;2-&gt;6-&gt;3-&gt;4-&gt;5-&gt;6, <em><strong>val</strong></em> = 6<br><strong>输出:</strong> 1-&gt;2-&gt;3-&gt;4-&gt;5</p>
<p><strong>解法一：</strong><br>双指针 + 虚拟头节点</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">removeElements</span><span class="params">(ListNode head, <span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">       <span class="keyword">if</span> (head == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">       ListNode dummyHead = <span class="keyword">new</span> ListNode(<span class="number">0</span>);</span><br><span class="line">       <span class="comment">//再头接待你之前加了新的节点</span></span><br><span class="line">       dummyHead.next = head;</span><br><span class="line">       ListNode pre = dummyHead, cur = head;</span><br><span class="line">       <span class="keyword">while</span> (cur != <span class="keyword">null</span>) &#123;</span><br><span class="line">           <span class="keyword">if</span> (cur.val == val) &#123;</span><br><span class="line">               pre.next = cur.next;</span><br><span class="line">           &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">               <span class="comment">//不是相等的值就向后移动</span></span><br><span class="line">               pre = cur;</span><br><span class="line">           &#125;</span><br><span class="line">           cur = cur.next;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="keyword">return</span> dummyHead.next;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二：</strong></p>
<p>递归方法比较简洁</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">removeElements2</span><span class="params">(ListNode head, <span class="keyword">int</span> val)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="keyword">null</span>)</span><br><span class="line">       <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//将下一个元素放进递归如果是==val的就会把下一个的下一个元素返回连接到当前元素</span></span><br><span class="line">    head.next = removeElements2(head.next, val);</span><br><span class="line">    <span class="keyword">return</span> head.val == val ? head.next : head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="19-删除链表的倒数第N个节点"><a href="#19-删除链表的倒数第N个节点" class="headerlink" title="19. 删除链表的倒数第N个节点"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list" >19. 删除链表的倒数第N个节点<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。<br>示例：<br>给定一个链表: 1-&gt;2-&gt;3-&gt;4-&gt;5, 和 n = 2.<br>当删除了倒数第二个节点后，链表变为 1-&gt;2-&gt;3-&gt;5.<br>说明：<br>给定的 n 保证是有效的。<br>进阶：<br>你能尝试使用一趟扫描实现吗？</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">removeNthFromEnd</span><span class="params">(ListNode head, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>&amp;&amp;head.next==<span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//双指针 主要是头和尾的删除需要抠一下边界</span></span><br><span class="line">    <span class="comment">//  -1 | 1 2 3 4 5 6</span></span><br><span class="line">    ListNode fast=head;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    ListNode slow=dummyNode;</span><br><span class="line">    <span class="comment">//加了哑节点，直接先加1</span></span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(fast!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        fast=fast.next;</span><br><span class="line">        slow=count&lt;n?slow:slow.next;</span><br><span class="line">        count++;</span><br><span class="line">        <span class="keyword">if</span>(fast.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="comment">//slow到达需要删除的位置的前一个</span></span><br><span class="line">            slow.next=slow.next.next;</span><br><span class="line">            <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>看了评论才知道咋一遍循环，主要就是控制slow指针走<code>length-n</code>步，让快指针先走n步，然后快慢一起走，快指针到头时慢指针就到<code>length-n</code>的位置了，这题也可以用List保存每个节点让然后把待删除的节点的前一个拿出来操作，遍历两遍的方法比较简单就不写了，感觉这种方法比较好 , 这题的OJ case比较少所以没什么可比性 , 前几个都是跑了两遍的，我把最快的拷过来跑的比我还慢。。。。然后我又提交了一次 beat 90%…….</p>
<h2 id="82-删除排序链表中的重复元素Ⅱ"><a href="#82-删除排序链表中的重复元素Ⅱ" class="headerlink" title="82. 删除排序链表中的重复元素Ⅱ"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii" >82. 删除排序链表中的重复元素Ⅱ<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中<strong>没有重复出现</strong>的数字。</p>
<p><strong>示例 1:</strong></p>
<p>输入: 1-&gt;2-&gt;3-&gt;3-&gt;4-&gt;4-&gt;5<br>输出: 1-&gt;2-&gt;5</p>
<p><strong>示例 2:</strong></p>
<p>输入: 1-&gt;1-&gt;1-&gt;2-&gt;3<br>输出: 2-&gt;3</p>
<p><strong>解法一</strong></p>
<p>乍一看跟上面那一题一样？这题是排序链表上面那题是无序的，而且这题不给定元素</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span>  <span class="keyword">static</span> ListNode <span class="title">deleteDuplicates</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>)<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//首先想到的思路是3指针，然后遍历的过程中后面的指针遇到==val的情况就让后面的指针一直后移走到！=val</span></span><br><span class="line">    <span class="comment">//先添加个哑节点</span></span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    ListNode cur=head;</span><br><span class="line">    ListNode next=head.next;</span><br><span class="line">    ListNode pre=dummyNode;</span><br><span class="line">    <span class="keyword">while</span>(next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">while</span>(next.val==cur.val)&#123;</span><br><span class="line">            next=next.next;</span><br><span class="line">            <span class="keyword">if</span>(next==<span class="keyword">null</span>)&#123;</span><br><span class="line">                pre.next=<span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(next.val!=cur.val)&#123;</span><br><span class="line">                pre.next=next;</span><br><span class="line">                <span class="comment">//cur跟上</span></span><br><span class="line">                cur=next;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//关键就是pre移动这里有坑 不能直接将pre移到cur,因为会有连续的连续存在</span></span><br><span class="line">        pre=cur.next!=<span class="keyword">null</span>&amp;&amp;cur.val==cur.next.val?pre:cur;</span><br><span class="line">        cur=next;</span><br><span class="line">        next=next.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>整体来说还是挺简单的只跑了一趟 1ms beta98%，评论里面大都只用了两个指针我用了三个这样感觉比较清晰<br>怎么好理解怎么来。貌似最快的是一个递归的，递归写起来确实玄学还要多练练啊</p>
<p><strong>解法二</strong></p>
<p>2020.4.2重写了一个递归的，感觉良好</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">deleteDuplicates</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span> || head.next==<span class="keyword">null</span>) <span class="keyword">return</span> head;</span><br><span class="line">    <span class="keyword">if</span>(head.val==head.next.val)&#123;</span><br><span class="line">        <span class="keyword">while</span>(head!=<span class="keyword">null</span> &amp;&amp; head.next!=<span class="keyword">null</span> &amp;&amp; head.val==head.next.val)&#123;</span><br><span class="line">            head=head.next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> deleteDuplicates(head.next); <span class="comment">//去重</span></span><br><span class="line">    &#125;</span><br><span class="line">    head.next=deleteDuplicates(head.next);</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="83-删除排序链表中的重复元素"><a href="#83-删除排序链表中的重复元素" class="headerlink" title="83. 删除排序链表中的重复元素"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/" >83. 删除排序链表中的重复元素<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">1</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span></span><br><span class="line">输出: <span class="number">1</span>-&gt;<span class="number">2</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">1</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">3</span></span><br><span class="line">输出: <span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>老题新写</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//递归</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">deleteDuplicates</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span> || head.next==<span class="keyword">null</span>) <span class="keyword">return</span> head;</span><br><span class="line">    ListNode node=deleteDuplicates(head.next);</span><br><span class="line">    <span class="keyword">if</span>(head.val==node.val) &#123;</span><br><span class="line">        head.next=node.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//迭代</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">deleteDuplicates</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    ListNode temp = head;</span><br><span class="line">    <span class="keyword">while</span> (temp != <span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span> (temp.next == <span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (temp.next.val == temp.val)&#123;</span><br><span class="line">            temp.next = temp.next.next;</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            temp = temp.next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="面试题-02-01-移除重复节点"><a href="#面试题-02-01-移除重复节点" class="headerlink" title="面试题 02.01. 移除重复节点"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/remove-duplicate-node-lcci/" >面试题 02.01. 移除重复节点<i class="fas fa-external-link-alt"></i></a></h2><p>编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。</p>
<p><strong>示例1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">3</span>, <span class="number">2</span>, <span class="number">1</span>]</span><br><span class="line">输出：[<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>, <span class="number">1</span>, <span class="number">2</span>]</span><br><span class="line">输出：[<span class="number">1</span>, <span class="number">2</span>]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li> 链表长度在[0, 20000]范围内。</li>
<li> 链表元素在[0, 20000]范围内。</li>
</ol>
<p><strong>进阶：</strong></p>
<p>如果不得使用临时缓冲区，该怎么解决？</p>
<p><strong>解法一</strong></p>
<p>无序链表，和前面不太一样，开个20000的数组判断是否重复就行了</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for singly-linked list.</span></span><br><span class="line"><span class="comment"> * type ListNode struct &#123;</span></span><br><span class="line"><span class="comment"> *     Val int</span></span><br><span class="line"><span class="comment"> *     Next *ListNode</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">removeDuplicateNodes</span><span class="params">(head *ListNode)</span> *<span class="title">ListNode</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> set = <span class="built_in">make</span>([]<span class="keyword">bool</span>,<span class="number">20001</span>)</span><br><span class="line">    <span class="keyword">var</span> dummyNode = &amp;ListNode&#123;Next:head&#125;</span><br><span class="line">    <span class="keyword">var</span> pre = dummyNode</span><br><span class="line">    <span class="keyword">for</span> head!=<span class="literal">nil</span>&#123;</span><br><span class="line">        <span class="keyword">if</span> !set[head.Val]&#123;</span><br><span class="line">            set[head.Val]=<span class="literal">true</span></span><br><span class="line">            pre=head</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            pre.Next=head.Next</span><br><span class="line">        &#125;</span><br><span class="line">        head=head.Next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.Next</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p>这个进阶或许应该称之为退阶。。。进阶的应该只能暴力O(N^2)而且这个数据量肯定会T，排序的话并没有合适的排序方法</p>
</blockquote>
<h2 id="143-重排链表"><a href="#143-重排链表" class="headerlink" title="143. 重排链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reorder-list/" >143. 重排链表<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个单链表 _L_：L0→L1→…→Ln-1→Ln<br>将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…</p>
<p>你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</p>
<p><strong>示例 1:</strong></p>
<p>给定链表 1-&gt;2-&gt;3-&gt;4, 重新排列为 1-&gt;4-&gt;2-&gt;3.</p>
<p><strong>示例 2:</strong></p>
<p>给定链表 1-&gt;2-&gt;3-&gt;4-&gt;5, 重新排列为 1-&gt;5-&gt;2-&gt;4-&gt;3.</p>
<blockquote>
<p>这题和上面的回文链表有点类似，都是快慢指针不过这题稍微复杂点</p>
</blockquote>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">reorderList</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    ListNode right = head;</span><br><span class="line">    ListNode slow = head;</span><br><span class="line">    <span class="comment">// 1 1 1 1 1 1 1</span></span><br><span class="line">    <span class="keyword">while</span> (right.next != <span class="keyword">null</span>) &#123;</span><br><span class="line">        right = right.next.next != <span class="keyword">null</span> ? right.next.next : right.next;</span><br><span class="line">        slow = slow.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 从slow开始翻转</span></span><br><span class="line">    res(slow);</span><br><span class="line">    <span class="comment">//左半部分</span></span><br><span class="line">    ListNode left = head;</span><br><span class="line">    <span class="comment">//下一个节点</span></span><br><span class="line">    ListNode rnext = right;</span><br><span class="line">    ListNode lnext = left;</span><br><span class="line">    <span class="comment">// 1 2 3 4 5 6 7 8 </span></span><br><span class="line">    <span class="comment">// 1 8 2 7 3 6 4 5</span></span><br><span class="line">    <span class="keyword">while</span> (right != <span class="keyword">null</span> &amp;&amp; left != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// 要保存right的下一个节点 , left也需要,不然无法导航到下一个节点</span></span><br><span class="line">        lnext = lnext.next;</span><br><span class="line">        rnext = rnext.next;</span><br><span class="line">        <span class="comment">// 偶数个数节点,如果遍历到right链表的最后一个节点</span></span><br><span class="line">        <span class="comment">// 偶数的话right链表会短一点 最后连接的时候</span></span><br><span class="line">        <span class="comment">// left: 1-&gt;2-&gt;3-&gt;4-&gt;5 right: 8-&gt;7-&gt;6-&gt;5   </span></span><br><span class="line">        <span class="comment">// 像这样会将5加到left的4和5之间,但是明显只有一个5这样添加就是有问题的</span></span><br><span class="line">        <span class="keyword">if</span>(right.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="comment">//所以这里吧lnext赋值为null,后面就不会重复连接5这个节点</span></span><br><span class="line">            lnext=<span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//奇数个数的时候这样连接没问题</span></span><br><span class="line">        <span class="comment">// 1 2 3 4 5 </span></span><br><span class="line">        <span class="comment">// 9 8 7 6 5</span></span><br><span class="line">        <span class="comment">//5.next=5</span></span><br><span class="line">        left.next = right;</span><br><span class="line">        <span class="comment">//如果奇数个数到最后这一步 right和left是同一个节点都为值是5的节点</span></span><br><span class="line">        <span class="comment">//所以这里下面的直接覆盖了上面的</span></span><br><span class="line">        <span class="comment">//5.next=null</span></span><br><span class="line">        right.next = lnext;</span><br><span class="line">        left = lnext;</span><br><span class="line">        right = rnext;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//反转</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">res</span><span class="params">(ListNode node)</span> </span>&#123;</span><br><span class="line">    ListNode pre = <span class="keyword">null</span>;</span><br><span class="line">    ListNode cur = node;</span><br><span class="line">    ListNode nex = node;</span><br><span class="line">    <span class="keyword">while</span> (cur != <span class="keyword">null</span>) &#123;</span><br><span class="line">        nex = nex.next;</span><br><span class="line">        cur.next = pre;</span><br><span class="line">        pre = cur;</span><br><span class="line">        cur = nex;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>也是之前的代码了，写的比较烂，但是思路还是比较清晰的，边界需要注意，速度还行 4ms  77% 。</p>
<h2 id="21-合并两个有序链表"><a href="#21-合并两个有序链表" class="headerlink" title="21. 合并两个有序链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/merge-two-sorted-lists/" >21. 合并两个有序链表<i class="fas fa-external-link-alt"></i></a></h2><p>将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 </p>
<p><strong>示例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入： <span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">4</span>, <span class="number">1</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span></span><br><span class="line">输出： <span class="number">1</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>常规迭代的做法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"> <span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeTwoLists</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">        ListNode temp=<span class="keyword">new</span> ListNode(<span class="number">0</span>);</span><br><span class="line">        ListNode res=temp;</span><br><span class="line">        <span class="keyword">while</span>(l1!=<span class="keyword">null</span>&amp;&amp;l2!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(l2.val&lt;l1.val)&#123;</span><br><span class="line">                temp.next=l2;</span><br><span class="line">                l2=l2.next;</span><br><span class="line">                temp=temp.next;</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                temp.next=l1;</span><br><span class="line">                l1=l1.next;</span><br><span class="line">                temp=temp.next;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        temp.next=l1==<span class="keyword">null</span>?l2:l1;</span><br><span class="line">        <span class="keyword">return</span> res.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>归并分治的思想，期末考试的一道题</p>
<p><strong>解法二</strong></p>
<p>递归的做法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeTwoLists</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    mergeTwoLists(l1,l2,dummyNode);</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">mergeTwoLists</span><span class="params">(ListNode l1, ListNode l2,ListNode res)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l1==<span class="keyword">null</span>)&#123;</span><br><span class="line">        res.next=l2;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(l2==<span class="keyword">null</span>)&#123;</span><br><span class="line">        res.next=l1;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(l1.val&gt;l2.val)&#123;</span><br><span class="line">        res.next=l2;</span><br><span class="line">        mergeTwoLists(l1,l2.next,res.next);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        res.next=l1;</span><br><span class="line">        mergeTwoLists(l1.next,l2,res.next);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>上面是我一开始自己写的，一点也不递归</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeTwoLists</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l1==<span class="keyword">null</span>) <span class="keyword">return</span> l2;</span><br><span class="line">    <span class="keyword">if</span>(l2==<span class="keyword">null</span>) <span class="keyword">return</span> l1;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">if</span>(l1.val&lt;l2.val)&#123;</span><br><span class="line">        l1.next=mergeTwoLists(l1.next,l2);</span><br><span class="line">        <span class="keyword">return</span> l1;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        l2.next=mergeTwoLists(l1,l2.next);</span><br><span class="line">        <span class="keyword">return</span> l2;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这种看着就很简洁</p>
<hr>
<h2 id="23-合并K个排序链表"><a href="#23-合并K个排序链表" class="headerlink" title="23. 合并K个排序链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/merge-k-sorted-lists/" >23. 合并K个排序链表<i class="fas fa-external-link-alt"></i></a></h2><p>合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">[</span><br><span class="line">  <span class="number">1</span>-&gt;<span class="number">4</span>-&gt;<span class="number">5</span>,</span><br><span class="line">  <span class="number">1</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>,</span><br><span class="line">  <span class="number">2</span>-&gt;<span class="number">6</span></span><br><span class="line">]</span><br><span class="line">输出: <span class="number">1</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;<span class="number">4</span>-&gt;<span class="number">5</span>-&gt;<span class="number">6</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeKLists</span><span class="params">(ListNode[] lists)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(lists.length==<span class="number">0</span>)<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    ListNode temp=lists[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;lists.length-<span class="number">1</span>;i++)&#123;</span><br><span class="line">        temp=merge2List(temp,lists[i+<span class="number">1</span>]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> temp;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">merge2List</span><span class="params">(ListNode headA,ListNode headB)</span></span>&#123;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    ListNode res=dummyNode;</span><br><span class="line">    ListNode tempA=headA;</span><br><span class="line">    ListNode tempB=headB;</span><br><span class="line">    <span class="keyword">while</span>(tempB!=<span class="keyword">null</span>&amp;&amp;tempA!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(tempB.val&gt;tempA.val)&#123;</span><br><span class="line">            res.next=tempA;</span><br><span class="line">            tempA=tempA.next;</span><br><span class="line">        &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">            res.next=tempB;</span><br><span class="line">            tempB=tempB.next;</span><br><span class="line">        &#125;</span><br><span class="line">        res=res.next;</span><br><span class="line">    &#125;</span><br><span class="line">    res.next=tempA==<span class="keyword">null</span>?tempB:tempA;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>最先想到的方法，和前面的二路归并一样，把前两个归并的结果和后面的继续归并。速度太慢了200ms左右…..时间复杂度是<code>O(N^2)</code>.<br><strong>解法二：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeKLists2</span><span class="params">(ListNode[] lists)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(lists.length==<span class="number">0</span>)<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">return</span> divide(lists,<span class="number">0</span>,lists.length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">divide</span><span class="params">(ListNode[] lists,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left&gt;=right)<span class="keyword">return</span> lists[left];</span><br><span class="line">    <span class="keyword">int</span> mid=left+((right-left)&gt;&gt;<span class="number">1</span>);</span><br><span class="line">    ListNode l = divide(lists,left,mid);</span><br><span class="line">    ListNode r = divide(lists,mid+<span class="number">1</span>,right);</span><br><span class="line">    <span class="keyword">return</span> merge2List(l,r);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">merge2List</span><span class="params">(ListNode headA,ListNode headB)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(headA==<span class="keyword">null</span>)<span class="keyword">return</span> headB;</span><br><span class="line">    <span class="keyword">if</span>(headB==<span class="keyword">null</span>)<span class="keyword">return</span> headA;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    ListNode res=dummyNode;</span><br><span class="line">    ListNode tempA=headA;</span><br><span class="line">    ListNode tempB=headB;</span><br><span class="line">    <span class="keyword">while</span>(tempB!=<span class="keyword">null</span>&amp;&amp;tempA!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(tempB.val&gt;tempA.val)&#123;</span><br><span class="line">            res.next=tempA;</span><br><span class="line">            tempA=tempA.next;</span><br><span class="line">        &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">            res.next=tempB;</span><br><span class="line">            tempB=tempB.next;</span><br><span class="line">        &#125;</span><br><span class="line">        res=res.next;</span><br><span class="line">    &#125;</span><br><span class="line">    res.next=tempA==<span class="keyword">null</span>?tempB:tempA;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>看起来很眼熟？没错就是归并排序的思路，利用分治的思想，先归并左边，再归并右边，然后merge左右的结果，时间复杂度为<code>O(NlogK)</code> (递归树深度为logK，归并每一层时间复杂度都是N)， 10ms左右，N是所有链表的元素个数，K是链表个数。而且因为是链表空间复杂度也不高。另外这题也可以改成非递归的方式如下:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeKLists3</span><span class="params">(ListNode [] lists)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (lists.length == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> k = lists.length;</span><br><span class="line">    <span class="keyword">while</span> (k &gt; <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; k / <span class="number">2</span>; i++) &#123;</span><br><span class="line">            <span class="comment">//两两合并将结果保存在前半部分的节点中然后缩小一半的范围</span></span><br><span class="line">            lists[i] = merge2Lists(lists[i], lists[i + (k + <span class="number">1</span>) / <span class="number">2</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//缩小一半的范围</span></span><br><span class="line">        k = (k + <span class="number">1</span>) / <span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> lists[<span class="number">0</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法三：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//小根堆的方法</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">mergeKLists4</span><span class="params">(ListNode[] lists)</span> </span>&#123;</span><br><span class="line">    <span class="comment">//利用一个按节点值最小次序排列的优先队列, 每次取最小的节点加入返回链表中</span></span><br><span class="line">    <span class="keyword">if</span>(lists.length &lt; <span class="number">1</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    Queue&lt;ListNode&gt; pq = <span class="keyword">new</span> PriorityQueue&lt;&gt;((a, b) -&gt; (a.val - b.val));</span><br><span class="line">    ListNode head = <span class="keyword">new</span> ListNode(<span class="number">0</span>);</span><br><span class="line">    ListNode cur = head;</span><br><span class="line">    <span class="keyword">for</span> (ListNode p : lists)&#123;</span><br><span class="line">        <span class="keyword">if</span>(p != <span class="keyword">null</span>)</span><br><span class="line">        pq.offer(p);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!pq.isEmpty()) &#123;</span><br><span class="line">        cur.next = pq.poll();</span><br><span class="line">        cur = cur.next;</span><br><span class="line">        <span class="keyword">if</span>(cur.next != <span class="keyword">null</span>)</span><br><span class="line">        <span class="comment">//讲当前节点后一个节点加入队列</span></span><br><span class="line">        pq.offer(cur.next);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>利用了小根堆，Java里面有小根堆可以直接用，思路就是每次把每条链表的头元素都放进小根堆里面然后找出最小的加到新链表中然后，最小的那个节点的链表向后移再加到小根堆里面，方法还是相当简洁的。但是用了90ms左右比较慢，时间复杂度<code>O(NlogK)</code>和上面是一样的，每次调整时间复杂度都是<code>logK</code>，需要调整<code>N</code>次(K为链表数量，N为所有链表的元素个数)，空间复杂度是 <code>O(K)</code></p>
<h2 id="355-设计推特"><a href="#355-设计推特" class="headerlink" title="355. 设计推特"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/design-twitter/" >355. 设计推特<i class="fas fa-external-link-alt"></i></a></h2><p>设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：</p>
<ol>
<li><strong>postTweet(userId, tweetId):</strong> 创建一条新的推文</li>
<li><strong>getNewsFeed(userId):</strong> 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。</li>
<li><strong>follow(followerId, followeeId):</strong> 关注一个用户</li>
<li><strong>unfollow(followerId, followeeId):</strong> 取消关注一个用户</li>
</ol>
<p><strong>实例</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">Twitter twitter = <span class="keyword">new</span> Twitter();</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户1发送了一条新推文 (用户id = 1, 推文id = 5).</span></span><br><span class="line">twitter.postTweet(<span class="number">1</span>, <span class="number">5</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.</span></span><br><span class="line">twitter.getNewsFeed(<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户1关注了用户2.</span></span><br><span class="line">twitter.follow(<span class="number">1</span>, <span class="number">2</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户2发送了一个新推文 (推文id = 6).</span></span><br><span class="line">twitter.postTweet(<span class="number">2</span>, <span class="number">6</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -&gt; [6, 5].</span></span><br><span class="line"><span class="comment">// 推文id6应当在推文id5之前，因为它是在5之后发送的.</span></span><br><span class="line">twitter.getNewsFeed(<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户1取消关注了用户2.</span></span><br><span class="line">twitter.unfollow(<span class="number">1</span>, <span class="number">2</span>);</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.</span></span><br><span class="line"><span class="comment">// 因为用户1已经不再关注用户2.</span></span><br><span class="line">twitter.getNewsFeed(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>其实核心就是一个k路链表的归并，这里直接用的优先级队列，然后用java8的新特性简化了代码</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Twitter</span> </span>&#123;</span><br><span class="line">    <span class="comment">//全局时间戳</span></span><br><span class="line">    <span class="keyword">private</span>  <span class="keyword">int</span> timeStamp=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//Tweet是有序链表,按照时间戳来排序</span></span><br><span class="line">    <span class="keyword">private</span>  Map&lt;Integer,Tweet&gt; userTweetMap=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="comment">//followMap</span></span><br><span class="line">    <span class="keyword">private</span>  Map&lt;Integer,Set&lt;Integer&gt;&gt; userFollowMap=<span class="keyword">new</span> HashMap&lt;&gt;();;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Twitter</span><span class="params">()</span> </span>&#123;&#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">postTweet</span><span class="params">(<span class="keyword">int</span> userId, <span class="keyword">int</span> tweetId)</span> </span>&#123;</span><br><span class="line">        Tweet oldHead=userTweetMap.get(userId);</span><br><span class="line">        userTweetMap.compute(userId,(k,v)-&gt;<span class="keyword">new</span> Tweet(tweetId,++timeStamp)).next=oldHead;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">getNewsFeed</span><span class="params">(<span class="keyword">int</span> userId)</span> </span>&#123;</span><br><span class="line">        PriorityQueue&lt;Tweet&gt; pq=<span class="keyword">new</span> PriorityQueue&lt;&gt;((t1,t2)-&gt;t2.time-t1.time);</span><br><span class="line">        List&lt;Integer&gt; feed=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        follow(userId,userId);</span><br><span class="line">        userFollowMap.get(userId).forEach(followerId-&gt;Optional.ofNullable(userTweetMap.get(followerId)).ifPresent(tw-&gt;pq.offer(tw)));</span><br><span class="line">        <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(!pq.isEmpty() &amp;&amp; count&lt;<span class="number">10</span>)&#123;</span><br><span class="line">            Tweet tw=pq.poll();</span><br><span class="line">            feed.add(tw.twId);</span><br><span class="line">            <span class="keyword">if</span>(tw.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">                pq.offer(tw.next);</span><br><span class="line">            &#125;</span><br><span class="line">            count++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> feed;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Follower follows a followee. If the operation is invalid, it should be a no-op. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">follow</span><span class="params">(<span class="keyword">int</span> followerId, <span class="keyword">int</span> followeeId)</span> </span>&#123;</span><br><span class="line">        userFollowMap.computeIfAbsent(followerId,k-&gt;<span class="keyword">new</span> HashSet&lt;&gt;()).add(followeeId);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unfollow</span><span class="params">(<span class="keyword">int</span> followerId, <span class="keyword">int</span> followeeId)</span> </span>&#123;</span><br><span class="line">        Optional.ofNullable(userFollowMap.get(followerId)).ifPresent(set-&gt;set.remove(followeeId));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Tweet</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> twId;</span><br><span class="line">    <span class="keyword">int</span> time;</span><br><span class="line">    Tweet next;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Tweet</span><span class="params">(<span class="keyword">int</span> twId,<span class="keyword">int</span> time)</span></span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.twId=twId;</span><br><span class="line">        <span class="keyword">this</span>.time=time;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="430-扁平化多级双向链表"><a href="#430-扁平化多级双向链表" class="headerlink" title="430. 扁平化多级双向链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list" >430. 扁平化多级双向链表<i class="fas fa-external-link-alt"></i></a></h2><p>您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。</p>
<p>扁平化列表，使所有结点出现在单级双链表中。您将获得列表第一级的头部。</p>
<p><strong>示例:</strong></p>
<p>输入:<br> 1—2—3—4—5—6–NULL<br>         |<br>         7—8—9—10–NULL<br>             |<br>             11–12–NULL</p>
<p>输出:<br>1-2-3-7-8-11-12-9-10-4-5-6-NULL</p>
<p><strong>说明:</strong></p>
<p>给出以下多级双向链表:</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/DqC2qKF5h63V.png?imageslim"
                      alt="mark"
                ></p>
<p>我们应该返回如下所示的扁平双向链表:</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/qOSn0TLmMuCt.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>解法一：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">        这种解法思路还是比较清晰的</span></span><br><span class="line"><span class="comment">        每次有子链的时候就直接把子链遍历到尾 然后添加到链表中形成新主链 把子链的入口节点child指定为null</span></span><br><span class="line"><span class="comment">        然后主链继续向后遍历所以整个遍历的次数就是整个链表元素的个数 O(M)</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">flatten1</span><span class="params">(Node head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span> || head.next==<span class="keyword">null</span>&amp;&amp;head.child==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> head;</span><br><span class="line">    &#125;</span><br><span class="line">    Node cur=head;</span><br><span class="line">    Node nNext;</span><br><span class="line">    Node child;</span><br><span class="line">    <span class="keyword">while</span>(cur!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(cur.child!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="comment">//有子链表</span></span><br><span class="line">            child=cur.child;</span><br><span class="line">            <span class="comment">//子链表的表头</span></span><br><span class="line">            nNext=cur.next;</span><br><span class="line">            <span class="comment">//主链的下一节点</span></span><br><span class="line">            <span class="comment">//连接子链表</span></span><br><span class="line">            cur.next=child;</span><br><span class="line">            <span class="comment">//主链的下一节点为子链表头</span></span><br><span class="line">            child.prev=cur;</span><br><span class="line">            <span class="comment">//子链表的前驱节点</span></span><br><span class="line">            <span class="comment">//已经拼接到主链，孩子链置为空 （这步还很关键我开始一直忘设置为null）</span></span><br><span class="line">            cur.child=<span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">if</span>(nNext==<span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="comment">//遍历到主链最后一个了</span></span><br><span class="line">                <span class="comment">//所以没有下一个节点，后面的步骤不用继续但是也不能Break 因为最后一个节点有可能还有子链表</span></span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">while</span>(child.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="comment">//找到新主链的下一节点 (子链的最后一个)</span></span><br><span class="line">                child=child.next;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//连接以前的主链</span></span><br><span class="line">            child.next=nNext;</span><br><span class="line">            nNext.prev=child;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//主链表向后移动</span></span><br><span class="line">        cur=cur.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法二：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//标准的DFS</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">flatten2</span><span class="params">(Node node)</span> </span>&#123;</span><br><span class="line">   <span class="keyword">if</span>(node==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line">    Node head = node;</span><br><span class="line">    <span class="keyword">while</span> (head!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="comment">//我感觉这样会快一些</span></span><br><span class="line">         Node next = head.next;</span><br><span class="line">        <span class="keyword">if</span>(head.child!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            next = head.next;</span><br><span class="line">            <span class="comment">//子链表扁平化 返回头节点</span></span><br><span class="line">            Node nextLayer = flatten2(head.child);<span class="comment">//子链表的头节点</span></span><br><span class="line">            <span class="comment">//连接子链表头和主链</span></span><br><span class="line">            head.next = nextLayer;</span><br><span class="line">            nextLayer.prev = head;</span><br><span class="line">            <span class="comment">//然后子链表置为null</span></span><br><span class="line">            head.child = <span class="keyword">null</span>;</span><br><span class="line">            <span class="comment">//遍历到子链表的结尾</span></span><br><span class="line">            <span class="keyword">while</span> (nextLayer.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">                nextLayer = nextLayer.next;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//连接子链表的尾部</span></span><br><span class="line">            nextLayer.next = next;</span><br><span class="line">            <span class="keyword">if</span>(next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">                next.prev = nextLayer;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//这里就直接跳过子链表 之前的是head=head.next; 但是因为之前的子链表已经加到主链表中所以会浪费一些时间（子链表肯定是已经扁平化的肯定都没有子链表）</span></span><br><span class="line">        head = next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>两种方法都是看的评论里面的第二种我稍微改了下，直接跳过子链表效率会高很多，不过这题case也比较少看不出差异。</p>
<hr>
<h2 id="141-环形链表"><a href="#141-环形链表" class="headerlink" title="141. 环形链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/linked-list-cycle" >141. 环形链表<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表，判断链表中是否有环。</p>
<p>为了表示给定链表中的环，我们使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：head = [<span class="number">3</span>,<span class="number">2</span>,<span class="number">0</span>,<span class="number">-4</span>], pos = <span class="number">1</span></span><br><span class="line">输出：<span class="literal">true</span></span><br><span class="line">解释：链表中有一个环，其尾部连接到第二个节点。</span><br></pre></td></tr></table></figure>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/H2wmyaG9uoiz.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>示例 2：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入： head = [<span class="number">1</span>,<span class="number">2</span>], pos = <span class="number">0</span></span><br><span class="line">输出： <span class="literal">true</span></span><br><span class="line">解释： 链表中有一个环，其尾部连接到第一个节点。</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/UqIc2XWwtxbo.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>示例 3：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入： head = [<span class="number">1</span>], pos = <span class="number">-1</span></span><br><span class="line">输出： <span class="literal">false</span></span><br><span class="line">解释： 链表中没有环。</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190303/dAg8QrxqJJga.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>进阶：</strong></p>
<p>你能用O(1)（即，常量）内存解决此问题吗？</p>
<p><strong>解法一</strong></p>
<p>有一点需要注意的是只有一个节点的情况应该是不考虑的直接 false</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Boolean <span class="title">hasCycle</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (head == <span class="keyword">null</span> || head.next == <span class="keyword">null</span>)</span><br><span class="line">                  <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="comment">//快慢指针 相遇的时候快指针回到头部step改为1 再次相遇的时候就是环的pos</span></span><br><span class="line">    <span class="comment">//这题只是判断有没有环所以只要相遇就有环</span></span><br><span class="line">    ListNode slow=head;</span><br><span class="line">    ListNode fast=head.next;</span><br><span class="line">    <span class="keyword">while</span>(slow!=fast)&#123;</span><br><span class="line">        <span class="comment">//有环是不会走到尽头的</span></span><br><span class="line">        <span class="keyword">if</span>(fast.next==<span class="keyword">null</span> || fast.next.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        fast=fast.next.next;</span><br><span class="line">        slow=slow.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="141-环形链表Ⅱ"><a href="#141-环形链表Ⅱ" class="headerlink" title="141. 环形链表Ⅱ"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/linked-list-cycle-ii/" >141. 环形链表Ⅱ<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 <code>null</code>。</p>
<p>为了表示给定链表中的环，我们使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。</p>
<p><strong>说明：</strong> 不允许修改给定的链表。 ps:上题的基础上返回入环的第一个节点</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">//UPDATE：2020.9.7 实行重写所有链表题的计划</span></span><br><span class="line"><span class="comment">// A--&gt;B--&gt;C--&gt;D   B为入环点，D为相遇点，相遇时slow = AD, fast = AD+DB+BD</span></span><br><span class="line"><span class="comment">// fast = 2*slow ==&gt; AD = DB + BD ==&gt; AB+BD = DB+BD ==&gt; AB = DB</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">detectCycle</span><span class="params">(head *ListNode)</span> *<span class="title">ListNode</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> fast, slow = head, head</span><br><span class="line">    <span class="keyword">for</span> fast!=<span class="literal">nil</span> &amp;&amp; fast.Next!=<span class="literal">nil</span> &#123;</span><br><span class="line">        fast = fast.Next.Next</span><br><span class="line">        slow = slow.Next</span><br><span class="line">        <span class="keyword">if</span> fast == <span class="literal">nil</span> &#123; <span class="comment">//无环</span></span><br><span class="line">            <span class="keyword">return</span> <span class="literal">nil</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> fast == slow &#123; <span class="comment">//有环，next一定不为null</span></span><br><span class="line">            <span class="keyword">for</span> head!=fast &#123;</span><br><span class="line">                head = head.Next</span><br><span class="line">                fast = fast.Next</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> head</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">nil</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p>这种解法还是挺有意思的<code>快慢指针</code>，快指针一次走两步慢指针一次走一步在环上相遇的时候快指针回到头节点步数调整为1，再&gt;次相遇的&gt;时候（这里有可能重合，当头节点就是入环节点的时候）就是入环节点。<br>原理 :<br>A—-&gt;B—-&gt;C      分别为<code>头节点</code>，<code>入环节点</code>，<code>第一次相遇的节点</code><br>分析第一次相遇时快慢指针走过的路径可得<br>AB+BC+CB+BC=2(AB+BC)  快指针走过的路程肯定是慢指针的两倍<br>化简最后就得到AB=CB 所以他们<code>再次相遇</code>就是入环的节点</p>
</blockquote>
<hr>
<h2 id="61-旋转链表"><a href="#61-旋转链表" class="headerlink" title="61.旋转链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/rotate-list/" >61.旋转链表<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表，旋转链表，将链表每个节点向右移动  k个位置，其中 k是非负数。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;<span class="number">5</span>-&gt;NULL, k = <span class="number">2</span></span><br><span class="line">输出: <span class="number">4</span>-&gt;<span class="number">5</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;NULL</span><br><span class="line">解释:</span><br><span class="line">向右旋转 <span class="number">1</span> 步: <span class="number">5</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;NULL</span><br><span class="line">向右旋转 <span class="number">2</span> 步: <span class="number">4</span>-&gt;<span class="number">5</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;NULL</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">0</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;NULL, k = <span class="number">4</span></span><br><span class="line">输出: <span class="number">2</span>-&gt;<span class="number">0</span>-&gt;<span class="number">1</span>-&gt;NULL</span><br><span class="line">解释:</span><br><span class="line">向右旋转 <span class="number">1</span> 步: <span class="number">2</span>-&gt;<span class="number">0</span>-&gt;<span class="number">1</span>-&gt;NULL</span><br><span class="line">向右旋转 <span class="number">2</span> 步: <span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">0</span>-&gt;NULL</span><br><span class="line">向右旋转 <span class="number">3</span> 步: <span class="number">0</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;NULL</span><br><span class="line">向右旋转 <span class="number">4</span> 步: <span class="number">2</span>-&gt;<span class="number">0</span>-&gt;<span class="number">1</span>-&gt;NULL</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">rotateRight</span><span class="params">(ListNode head, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> head;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//先获取下链表的长度，顺便记录tail的值</span></span><br><span class="line">    ListNode temp=head;</span><br><span class="line">    ListNode tail=head;</span><br><span class="line">    <span class="keyword">int</span> length=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        length++;</span><br><span class="line">        <span class="keyword">if</span>(temp.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            tail=temp;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//将K化简</span></span><br><span class="line">    k=k%length;</span><br><span class="line">    <span class="keyword">if</span>(k==<span class="number">0</span>) <span class="keyword">return</span> head;</span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//然后再遍历一遍链表在 length-k 的地方断开</span></span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(count==(length-k-<span class="number">1</span>))&#123;</span><br><span class="line">            tail.next=head;</span><br><span class="line">            head=temp.next;</span><br><span class="line">            temp.next=<span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">return</span> head;</span><br><span class="line">        &#125;</span><br><span class="line">        count++;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>虽然难度是mid，但是感觉这题还是比较简单，我看见有一种比较好点的方法是在第一遍循环完之后将链表转换为<code>双向链表</code>然后再移动还是比较有意思的</p>
<h2 id="328-奇偶链表"><a href="#328-奇偶链表" class="headerlink" title="328. 奇偶链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/odd-even-linked-list" >328. 奇偶链表<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。</p>
<p>请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。</p>
<p><strong>示例 1:</strong></p>
<p>输入: <code>1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;NULL</code><br>输出: <code>1-&gt;3-&gt;5-&gt;2-&gt;4-&gt;NULL</code></p>
<p><strong>示例 2:</strong></p>
<p>输入: <code>2-&gt;1-&gt;3-&gt;5-&gt;6-&gt;4-&gt;7-&gt;NULL</code><br>输出: <code>2-&gt;3-&gt;6-&gt;7-&gt;1-&gt;5-&gt;4-&gt;NULL</code></p>
<p><strong>说明:</strong></p>
<p>应当保持奇数节点和偶数节点的相对顺序。<br>链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//奇偶链表</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">oddEvenList</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>||head.next.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    <span class="comment">// 1 2 3 4 5 6 7</span></span><br><span class="line">    <span class="comment">// 1 2 3 4 5 6</span></span><br><span class="line">    ListNode pOdd=head;</span><br><span class="line">    ListNode pEven=head.next;</span><br><span class="line">    ListNode temp=pEven;</span><br><span class="line">    <span class="keyword">while</span>(pEven!=<span class="keyword">null</span>&amp;&amp;pEven.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        pOdd.next=pEven.next;</span><br><span class="line">        <span class="comment">//奇数先走</span></span><br><span class="line">        pOdd=pOdd.next;</span><br><span class="line">        pEven.next=pOdd.next;</span><br><span class="line">        pEven=pEven.next;</span><br><span class="line">    &#125;</span><br><span class="line">    pOdd.next=temp;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>很像踩石头过河的游戏，一道很简单的mid，不知道为啥一开始抠了半天的边界。。。果然</p>
<blockquote>
<p>还是不熟悉啊。Add oil ! ! !</p>
</blockquote>
<h2 id="147-对链表进行插入排序"><a href="#147-对链表进行插入排序" class="headerlink" title="147. 对链表进行插入排序"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/insertion-sort-list" >147. 对链表进行插入排序<i class="fas fa-external-link-alt"></i></a></h2><p>插入排序的动画演示如上篇文章。<br>每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。<br>插入排序算法：<br>插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。<br>每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。<br>重复直到所有输入数据插入完为止。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">4</span>-&gt;<span class="number">2</span>-&gt;<span class="number">1</span>-&gt;<span class="number">3</span></span><br><span class="line">输出: <span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: -<span class="number">1</span>-&gt;<span class="number">5</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;<span class="number">0</span></span><br><span class="line">输出: -<span class="number">1</span>-&gt;<span class="number">0</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;<span class="number">5</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//beat 50%</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span>  ListNode <span class="title">insertionSortList</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    <span class="comment">//哑节点</span></span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(Integer.MIN_VALUE);</span><br><span class="line">    System.out.println(dummyNode.val);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    ListNode tempNode=head;</span><br><span class="line">    <span class="comment">//外循环内的指针</span></span><br><span class="line">    ListNode loopVariable=head.next;</span><br><span class="line">    ListNode loopPre=head;</span><br><span class="line">    <span class="comment">//内循环的指针</span></span><br><span class="line">    ListNode tempPre=dummyNode;</span><br><span class="line">    <span class="keyword">while</span>(loopVariable!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="comment">//头插法</span></span><br><span class="line">        <span class="keyword">for</span> (tempNode=dummyNode;tempNode!=loopVariable;tempNode=tempNode.next)&#123;</span><br><span class="line">            <span class="keyword">if</span>(tempNode.val&gt;loopVariable.val)&#123;</span><br><span class="line">                <span class="comment">//System.out.println(loopVariable.val);</span></span><br><span class="line">                <span class="comment">//printList(dummyNode.next);</span></span><br><span class="line">                <span class="comment">//先处理好loopVariable的前后节点</span></span><br><span class="line">                loopPre.next=loopVariable.next;</span><br><span class="line">                <span class="comment">//再处理tempNode前后的节点</span></span><br><span class="line">                loopVariable.next=tempNode;</span><br><span class="line">                tempPre.next=loopVariable;</span><br><span class="line">                <span class="comment">//loopVariable 归位</span></span><br><span class="line">                loopVariable=loopPre;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            tempPre=tempNode;</span><br><span class="line">        &#125;</span><br><span class="line">        loopPre=loopVariable;</span><br><span class="line">        loopVariable=loopVariable.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>上面的是我开始自己写的，但是提交后发现速度有点慢40ms 50%左右 然后我有点不信把比较靠前的拷了一个 10ms😂前几名10ms以内的都是用的方法不是插入….<br>在研究别人10ms的代码时突然意识到了问题所在 我在进行插入的时候没有判断就时没有关心是不是应该进行插入操作，对于数组的插入排序是不用关心这个问题的，因为是反向遍历的 而这里是链表只能正向的遍历如果不判断就会浪费很多时间</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">// 16ms  beat  70% 开始少写了一个if判断</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span>  ListNode <span class="title">insertionSortList</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    <span class="comment">//哑节点</span></span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(Integer.MIN_VALUE);</span><br><span class="line">    System.out.println(dummyNode.val);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    ListNode tempNode=head;</span><br><span class="line">    <span class="comment">//外循环内的指针</span></span><br><span class="line">    ListNode loopVariable=head.next;</span><br><span class="line">    ListNode loopPre=head;</span><br><span class="line">    <span class="comment">//内循环的指针</span></span><br><span class="line">    ListNode tempPre=dummyNode;</span><br><span class="line">    <span class="keyword">while</span>(loopVariable!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="comment">//头插法</span></span><br><span class="line">        <span class="keyword">if</span>(loopVariable.val&lt;loopPre.val)&#123;</span><br><span class="line">            <span class="keyword">for</span> (tempNode=dummyNode;tempNode!=loopVariable;tempNode=tempNode.next)&#123;</span><br><span class="line">                <span class="keyword">if</span>(tempNode.val&gt;loopVariable.val)&#123;</span><br><span class="line">                    <span class="comment">//System.out.println(loopVariable.val);</span></span><br><span class="line">                    <span class="comment">//printList(dummyNode.next);</span></span><br><span class="line">                    <span class="comment">//先处理好loopVariable的前后节点</span></span><br><span class="line">                    loopPre.next=loopVariable.next;</span><br><span class="line">                    <span class="comment">//再处理tempNode前后的节点</span></span><br><span class="line">                    loopVariable.next=tempNode;</span><br><span class="line">                    tempPre.next=loopVariable;</span><br><span class="line">                    <span class="comment">//loopVariable 归位</span></span><br><span class="line">                    loopVariable=loopPre;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                tempPre=tempNode;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        loopPre=loopVariable;</span><br><span class="line">        loopVariable=loopVariable.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这题整体思路就是按照插入排序的思路来的，值得注意的就是链表只能正向遍历，而且需要考虑保存的节点有两个，插入位置的前一个，以及待插入的前一个(头插法)。</p>
<h2 id="148-排序链表"><a href="#148-排序链表" class="headerlink" title="148. 排序链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/sort-list" >148. 排序链表<i class="fas fa-external-link-alt"></i></a></h2><p>在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。</p>
<p><strong>示例 1:</strong></p>
<p>输入: 4-&gt;2-&gt;1-&gt;3<br>输出: 1-&gt;2-&gt;3-&gt;4<br>示例 2:</p>
<p>输入: -1-&gt;5-&gt;3-&gt;4-&gt;0<br>输出: -1-&gt;0-&gt;3-&gt;4-&gt;5</p>
<blockquote>
<p>上面那题时间复杂度明显是O(n2)最坏，这题要求是O(nlogn)和常数空间上面的插入肯定不适合了</p>
</blockquote>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//归并排法</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span>  ListNode <span class="title">sortList</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">return</span> mergeSort(head);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">mergeSort</span><span class="params">(ListNode head)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> head;</span><br><span class="line">    &#125;</span><br><span class="line">    ListNode fast=head;</span><br><span class="line">    ListNode slow=head;</span><br><span class="line">    ListNode pre=head;</span><br><span class="line">    <span class="keyword">while</span>(fast!=<span class="keyword">null</span>&amp;&amp;fast.next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        pre=slow;</span><br><span class="line">        fast=fast.next.next;</span><br><span class="line">        slow=slow.next;</span><br><span class="line">    &#125;</span><br><span class="line">    pre.next=<span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//这里要注意断开两条链表不然后面不方便找中点</span></span><br><span class="line">    ListNode left = mergeSort(head);</span><br><span class="line">    <span class="comment">//归并左边</span></span><br><span class="line">    ListNode right = mergeSort(slow);</span><br><span class="line">    <span class="comment">//归并右边</span></span><br><span class="line">    <span class="keyword">return</span> merge2list(left,right);</span><br><span class="line">    <span class="comment">//返回 左右两条链表归并结果</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">merge2list</span><span class="params">(ListNode headA,ListNode headB)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(headA==<span class="keyword">null</span>)<span class="keyword">return</span> headB;</span><br><span class="line">    <span class="keyword">if</span>(headB==<span class="keyword">null</span>)<span class="keyword">return</span> headA;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=headA;</span><br><span class="line">    ListNode temp=dummyNode;</span><br><span class="line">    <span class="keyword">while</span>(headA!=<span class="keyword">null</span>&amp;&amp;headB!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(headA.val&gt;headB.val)&#123;</span><br><span class="line">            temp.next=headB;</span><br><span class="line">            headB=headB.next;</span><br><span class="line">        &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">            temp.next=headA;</span><br><span class="line">            headA=headA.next;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    temp.next=headA==<span class="keyword">null</span>?headB:headA;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>4ms 85%  标准的<code>归并操作</code>分治的思想，但是我还是扣了好长时间，最后还是看了别人的代码才知道，其实一开始就想到了<code>快慢指针找中点</code>但是感觉时间复杂度可能会变得更高就没那样做。。。还是太菜了时间复杂度都不会分析。。。这里有一个小地方就是找到中点之后要记得断开中点和后面链表的连接，这样会方便后面归并，不然就需要传递一个边界的指针那样又会有很多问题（没错我开始就是这么做的😭）</p>
<p>下面这种是后来又写的<code>经典快排</code>，400ms，12% 我都怀疑我到底写了个啥？后来把插入拿来试了下884+ms然后又看了一遍才相信我写的是快排。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//我自己写的快排</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">sortList4</span><span class="params">(ListNode head)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    sortList(head,<span class="keyword">null</span>);</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//快排实现</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sortList</span><span class="params">(ListNode head,ListNode tail)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(tail==head)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//确定枢纽元素</span></span><br><span class="line">    ListNode base=partion(head,tail);</span><br><span class="line">    sortList(head,base);</span><br><span class="line">    sortList(base.next,tail);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//看了下别人的博客也学到了一种快排的新思路</span></span><br><span class="line"><span class="comment">//慢指针左边都是小于base枢纽元素的，快指针和慢指针中间都是大于等于base枢纽元素的</span></span><br><span class="line"><span class="comment">//慢指针后面的都是未知区域</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">partion</span><span class="params">(ListNode head,ListNode tail)</span></span>&#123;</span><br><span class="line">    ListNode base=head;</span><br><span class="line">    ListNode fast=head.next;</span><br><span class="line">    ListNode slow=head;</span><br><span class="line">    <span class="comment">// 3  1  3  2  5  -1 0</span></span><br><span class="line">    <span class="comment">//    s  f</span></span><br><span class="line">    <span class="keyword">while</span>(fast!=tail)&#123;</span><br><span class="line">        <span class="keyword">if</span>(fast.val&lt;=base.val)&#123;</span><br><span class="line">            <span class="comment">//交换两个节点的值</span></span><br><span class="line">            swap(fast,slow.next);</span><br><span class="line">            slow=slow.next;</span><br><span class="line">        &#125;</span><br><span class="line">        fast=fast.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//归位</span></span><br><span class="line">    swap(head,slow);</span><br><span class="line">    <span class="comment">//应该可以试试返回区间</span></span><br><span class="line">    <span class="keyword">return</span> slow;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(ListNode a,ListNode b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> temp=a.val;</span><br><span class="line">    a.val=b.val;</span><br><span class="line">    b.val=temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>实际上快排确实不适合链表（下面光速打脸）因为毕竟不是数组可以从两边开始遍历，链表每次都需要遍历整个链表才能划分好基准位置。</p>
</blockquote>
<p>看了下前几的代码发现了这个，<code>非标准的三向切分的快排</code>，为啥说是非标准呢？看下面代码就知道了，我给加了注释</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">sortList3</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    ListNode node = <span class="keyword">new</span> ListNode(<span class="number">0</span>);</span><br><span class="line">    node.next = head;</span><br><span class="line">    sort(node, <span class="keyword">null</span>);</span><br><span class="line">    <span class="keyword">return</span> node.next;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span>  <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(ListNode from, ListNode to)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (from == <span class="keyword">null</span> || from == to || from.next == to || from.next.next == to)<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">int</span> v = from.next.val;</span><br><span class="line">    <span class="comment">//基准元素</span></span><br><span class="line">    ListNode mid = from;</span><br><span class="line">    <span class="comment">//切分点指针</span></span><br><span class="line">    ListNode equal = from.next;</span><br><span class="line">    <span class="comment">//等于区域右边界</span></span><br><span class="line">    ListNode node = from.next;</span><br><span class="line">    <span class="comment">//遍历用的指针</span></span><br><span class="line">    <span class="keyword">while</span> (node.next != to) &#123;</span><br><span class="line">        <span class="comment">//node不到头  左开右开区间（from,to）</span></span><br><span class="line">        <span class="keyword">if</span> (node.next.val &lt; v) &#123;</span><br><span class="line">            <span class="comment">//小于基准位置元素</span></span><br><span class="line">            <span class="comment">//保存当前节点的下一个元素，用于插入节点</span></span><br><span class="line">            <span class="comment">//小于基准元素的节点</span></span><br><span class="line">            ListNode currentNext = node.next.next;</span><br><span class="line">            <span class="comment">//保存切分点的下一个元素，作用同上</span></span><br><span class="line">            ListNode midNext = mid.next;</span><br><span class="line">            <span class="comment">//交换node.next和mid</span></span><br><span class="line">            <span class="comment">//纸上画一下就了解了</span></span><br><span class="line">            mid.next = node.next;</span><br><span class="line">            node.next.next = midNext;</span><br><span class="line">            node.next = currentNext;</span><br><span class="line">            <span class="comment">//切分点后移</span></span><br><span class="line">            mid = mid.next;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.next.val == v) &#123;</span><br><span class="line">            <span class="comment">//node的下一个等于基准元素</span></span><br><span class="line">            <span class="comment">//3 1 2 3 4 5 6</span></span><br><span class="line">            <span class="keyword">if</span> (equal == node) &#123;</span><br><span class="line">                <span class="comment">//等于区域和node.next==val相邻了，直接跳过</span></span><br><span class="line">                equal = node.next;</span><br><span class="line">                node = node.next;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//将node.next插入equal后面</span></span><br><span class="line">                <span class="comment">//然后equal向后移动</span></span><br><span class="line">                <span class="comment">//和上面的类似</span></span><br><span class="line">                ListNode nodeNext = node.next.next;</span><br><span class="line">                ListNode equalNext = equal.next;</span><br><span class="line">                equal.next = node.next;</span><br><span class="line">                node.next.next = equalNext;</span><br><span class="line">                node.next = nodeNext;</span><br><span class="line">                equal = equal.next;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//大于直接跳过</span></span><br><span class="line">            node = node.next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// [mid.next---equal] 为等于val的节点</span></span><br><span class="line">    sort(from, mid.next);</span><br><span class="line">    sort(equal, to);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>整体思路就是一共有三个指针，<code>mid</code>(切分点)  <code>equal</code>(等于区) <code>node</code>(遍历指针) node从from遍历到to，注意这里是<code>左开右开区间</code> 就是说头from和尾to都取不到，然后将小与base的节点插入到mid的后面，然后mid后移，等于区插入到equal的后面，最后形成的就是<code>[mid.next---equal]</code> 为等于val的节点，然后对子区域递归就ok了，这个用时 <code>4ms</code> 。。。。。。还要继续加油啊！！！</p>
<h2 id="138-复制带随机指针的链表"><a href="#138-复制带随机指针的链表" class="headerlink" title="138.复制带随机指针的链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/copy-list-with-random-pointer" >138.复制带随机指针的链表<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。</p>
<p>要求返回这个链表的深拷贝。 </p>
<p><strong>示例：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190308/tR8e3eu2yqaq.png?imageslim"
                      alt="mark"
                ></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">输入：</span><br><span class="line">`&#123;<span class="string">&quot;$id&quot;</span>:<span class="string">&quot;1&quot;</span>,<span class="string">&quot;next&quot;</span>:&#123;<span class="string">&quot;$id&quot;</span>:<span class="string">&quot;2&quot;</span>,<span class="string">&quot;next&quot;</span>:null,<span class="string">&quot;random&quot;</span>:&#123;<span class="string">&quot;$ref&quot;</span>:<span class="string">&quot;2&quot;</span>&#125;,<span class="string">&quot;val&quot;</span>:<span class="number">2</span>&#125;,<span class="string">&quot;random&quot;</span>:&#123;<span class="string">&quot;$ref&quot;</span>:<span class="string">&quot;2&quot;</span>&#125;,<span class="string">&quot;val&quot;</span>:<span class="number">1</span>&#125;`</span><br><span class="line">解释：</span><br><span class="line">节点 <span class="number">1</span> 的值是 <span class="number">1</span>，它的下一个指针和随机指针都指向节点 <span class="number">2</span> 。</span><br><span class="line">节点 <span class="number">2</span> 的值是 <span class="number">2</span>，它的下一个指针指向 null，随机指针指向它自己。</span><br></pre></td></tr></table></figure>
<p><strong>提示：</strong></p>
<p>你必须返回给定头的拷贝作为对克隆列表的引用。</p>
<p><strong>解法一</strong> </p>
<p>利用Map保存原链表和复制链表的对应关系</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">copyRandomList</span><span class="params">(Node head)</span> </span>&#123;</span><br><span class="line">    Map&lt;Node,Node&gt; copNode =<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    Node temp=head;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="comment">//建立对应关系</span></span><br><span class="line">        copNode.put(temp,<span class="keyword">new</span> Node(temp.val,<span class="keyword">null</span>,<span class="keyword">null</span>));</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//再循环一次复制next和Radom节点</span></span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        copNode.get(temp).next=copNode.get(temp.next);</span><br><span class="line">        copNode.get(temp).random=copNode.get(temp.random);</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> copNode.get(head);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>第一个循环利用Map将原链表和拷贝链表形成对应关系，第二个循环就是直接给拷贝链表的next域和random域赋值。</p>
<p><strong>解法二</strong></p>
<p>奥义 影分身</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">copyRandomList2</span><span class="params">(Node head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    Node temp=head;</span><br><span class="line">    <span class="comment">//链表  奥义 - 影分身</span></span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="comment">//这里直接将next域传入构造器完成和后面元素的连接</span></span><br><span class="line">        temp.next=<span class="keyword">new</span> Node(temp.val,temp.next,<span class="keyword">null</span>);</span><br><span class="line">        temp=temp.next.next;</span><br><span class="line">    &#125;</span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="comment">//连接random域</span></span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(temp.random!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            temp.next.random=temp.random.next;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=temp.next.next;</span><br><span class="line">    &#125;</span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="comment">// 分离</span></span><br><span class="line">    Node newHead=head.next;</span><br><span class="line">    Node next=<span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123; <span class="comment">//=将每个元素的next指向下一个的下一个</span></span><br><span class="line">        next=temp.next;</span><br><span class="line">        <span class="keyword">if</span>(next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            temp.next=next.next;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> newHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>为啥要叫影分身？因为帅…这种方法比上面的要快一点可能是创建hashMap比较耗时间，其实分析这两种方法其实都是先把链表拷贝了一份，然后通过对应关系来连接拷贝链表的next和random域，map是通过键值对的方式对应拷贝链表，这样可以方便的通过原链表找到拷贝链表的random. 然后上面这种方法也是一样，在原链表每个节点后面copy一个节点，然后根据前一个节点的random来找拷贝节点的random(前一个节点的random的next) 主要就是找到一个对应关系.</p>
<blockquote>
<p>tips: 这题OJ上的0ms是有问题的，这题本意肯定也不是这个</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190308/p1GPgJVYaURp.png?imageslim"
                      alt="mark"
                ></p>
</blockquote>
<p>最开始能通过主要是OJ后台只判断了val的值，可以看出现在题目已经改了。现在肯定是跑不过的，可能是判断了random是不是new出来的(我试了下看了下返回这个)<br>输入<br><code>&#123;&quot;$id&quot;:&quot;1&quot;,&quot;next&quot;:&#123;&quot;$id&quot;:&quot;2&quot;,&quot;next&quot;:null,&quot;random&quot;:&#123;&quot;$ref&quot;:&quot;2&quot;&#125;,&quot;val&quot;:2&#125;,&quot;random&quot;:&#123;&quot;$ref&quot;:&quot;2&quot;&#125;,&quot;val&quot;:1&#125;</code><br>输出<br><code>&#123;&quot;$id&quot;:&quot;1&quot;,&quot;next&quot;:&#123;&quot;$id&quot;:&quot;2&quot;,&quot;next&quot;:null,&quot;random&quot;:</code></p>
<p><code>&#123;&quot;$id&quot;:&quot;3&quot;,&quot;next&quot;:null,&quot;random&quot;:null,&quot;val&quot;:2&#125;,&quot;val&quot;:2&#125;,</code></p>
<p><code>&quot;random&quot;:&#123;&quot;$id&quot;:&quot;4&quot;,&quot;next&quot;:null,&quot;random&quot;:null,&quot;val&quot;:2&#125;,&quot;val&quot;:1&#125;</code><br>预期结果<br><code>&#123;&quot;$id&quot;:&quot;1&quot;,&quot;next&quot;:&#123;&quot;$id&quot;:&quot;2&quot;,&quot;next&quot;:null,&quot;random&quot;:&#123;&quot;$ref&quot;:&quot;2&quot;&#125;,&quot;val&quot;:2&#125;,&quot;random&quot;:&#123;&quot;$ref&quot;:&quot;2&quot;&#125;,&quot;val&quot;:1&#125;</code></p>
<p><strong>解法三</strong></p>
<p>重写了一遍，题目改了一点</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> Node <span class="title">copyRandomList</span><span class="params">(Node head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    Node temp=head;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        Node next=temp.next;</span><br><span class="line">        Node newNode=<span class="keyword">new</span> Node(temp.val);</span><br><span class="line">        temp.next=newNode;</span><br><span class="line">        newNode.next=next;</span><br><span class="line">        temp=next;</span><br><span class="line">    &#125;</span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="comment">//重写的时候想把random连接和分离一起做</span></span><br><span class="line">    <span class="comment">//然后就错了。。。</span></span><br><span class="line">    <span class="comment">//这里next域的变化就会导致后面random域的变化，最后结果就错了</span></span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        Node next=temp.next.next;</span><br><span class="line">        <span class="keyword">if</span>(temp.random!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            temp.next.random=temp.random.next;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=next;</span><br><span class="line">    &#125;</span><br><span class="line">    Node newHead=head.next;</span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="comment">//将每个元素的next域指向下一个的下一个就行了</span></span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        Node next=temp.next;</span><br><span class="line">        <span class="keyword">if</span>(next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            temp.next=next.next;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> newHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="24-两两交换链表中的节点"><a href="#24-两两交换链表中的节点" class="headerlink" title="24. 两两交换链表中的节点"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/swap-nodes-in-pairs/" >24. 两两交换链表中的节点<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。</p>
<p>你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</p>
<p><strong>示例:</strong></p>
<p>给定 1-&gt;2-&gt;3-&gt;4, 你应该返回 2-&gt;1-&gt;4-&gt;3.</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">swapPairs</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    ListNode nex=head.next;</span><br><span class="line">    ListNode cur=head;</span><br><span class="line">    ListNode pre=dummyNode;</span><br><span class="line">    <span class="comment">// -1|1 2 3 4</span></span><br><span class="line">    <span class="keyword">while</span>(nex!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        pre.next=nex;</span><br><span class="line">        cur.next=nex.next;</span><br><span class="line">        nex.next=cur;</span><br><span class="line">        pre=cur;</span><br><span class="line">        <span class="keyword">if</span>(cur.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">        &#125;</span><br><span class="line">        cur=cur.next;</span><br><span class="line">        nex=cur.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实跟反转链表是一样的，三个指针分别记录前 中 后三个节点然后逆序，只不过步长不一样，这里step为2，一次走两步， 我上面的代码可能写的有些乱，思路还是一样的</p>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//递归版本</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">swapPairs</span><span class="params">(ListNode head)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> head;</span><br><span class="line">    &#125;</span><br><span class="line">    ListNode next=head.next;</span><br><span class="line">    head.next=swapPairs(next.next);</span><br><span class="line">    next.next=head;</span><br><span class="line">    <span class="keyword">return</span> next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>递归是真的简洁，我最开始写反转链表的递归就是这么写的😂</p>
<h2 id="25-K个一组翻转链表"><a href="#25-K个一组翻转链表" class="headerlink" title="25.K个一组翻转链表"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-nodes-in-k-group/" >25.K个一组翻转链表<i class="fas fa-external-link-alt"></i></a></h2><p>给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。</p>
<p>k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。</p>
<p><strong>示例 :</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">给定这个链表：<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span>-&gt;<span class="number">5</span></span><br><span class="line">当 k = <span class="number">2</span> 时，应当返回: <span class="number">2</span>-&gt;<span class="number">1</span>-&gt;<span class="number">4</span>-&gt;<span class="number">3</span>-&gt;<span class="number">5</span></span><br><span class="line">当 k = <span class="number">3</span> 时，应当返回: <span class="number">3</span>-&gt;<span class="number">2</span>-&gt;<span class="number">1</span>-&gt;<span class="number">4</span>-&gt;<span class="number">5</span></span><br></pre></td></tr></table></figure>

<p><strong>说明 :</strong></p>
<ul>
<li>你的算法只能使用常数的额外空间。</li>
<li>你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//非递归，理一下思路： 记录每次翻转前后的节点 然后翻转返回头 将每 K 个元素当成一个整体</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">reverseKGroup</span><span class="params">(ListNode head,<span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>)<span class="keyword">return</span> head;</span><br><span class="line">    ListNode dummyNode=<span class="keyword">new</span> ListNode(-<span class="number">1</span>);</span><br><span class="line">    dummyNode.next=head;</span><br><span class="line">    ListNode pre=dummyNode;</span><br><span class="line">    ListNode cur=head;</span><br><span class="line">    ListNode next=head;</span><br><span class="line">    ListNode temp;</span><br><span class="line">    <span class="keyword">while</span>(next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="comment">//temp 保存 cur 方便后面连接  K+1位置的元素</span></span><br><span class="line">        temp=cur;</span><br><span class="line">        <span class="comment">//k 个一组翻转</span></span><br><span class="line">        <span class="keyword">int</span> step=k;</span><br><span class="line">        <span class="keyword">while</span>(step&gt;<span class="number">0</span> &amp;&amp; next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            <span class="comment">//next走到 K+1 位置节点</span></span><br><span class="line">            next=next.next;</span><br><span class="line">            step--;</span><br><span class="line">            <span class="comment">//小细节 k&gt;链表长度时应该直接返回（我认为）等下提交了看看</span></span><br><span class="line">            <span class="comment">//所以直接应该直接返回 (掉了k的值判断 因为有可能刚好有k个元素)</span></span><br><span class="line">            <span class="keyword">if</span>(next==<span class="keyword">null</span>&amp;&amp; step!=<span class="number">0</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//翻转 cur--next.prev 返回头节点</span></span><br><span class="line">        <span class="comment">//连接 反转后的头节点</span></span><br><span class="line">        pre.next=reverse(cur,k);</span><br><span class="line">        temp.next=next;</span><br><span class="line">        <span class="comment">//pre temp向后移动</span></span><br><span class="line">        pre=temp;</span><br><span class="line">        cur=next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.next;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// -1| 1 2 3 | 4 5 6 | 7 8</span></span><br><span class="line"><span class="comment">//翻转链表并返回子链表</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> ListNode <span class="title">reverse</span><span class="params">(ListNode node,<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">    ListNode pre=<span class="keyword">null</span>;</span><br><span class="line">    ListNode cur=node;</span><br><span class="line">    ListNode next=node;</span><br><span class="line">    <span class="keyword">while</span>(k&gt;<span class="number">0</span>&amp;&amp;next!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        next=next.next;</span><br><span class="line">        cur.next=pre;</span><br><span class="line">        pre=cur;</span><br><span class="line">        cur=next;</span><br><span class="line">        k--;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//返回反转后的头节点</span></span><br><span class="line">    System.out.println(<span class="string">&quot;头&quot;</span>+pre.val);</span><br><span class="line">    <span class="keyword">return</span> pre;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>7ms 74% 也是我第一道做出来的困难题，<a href="http://imlgw.top/2018/10/31/%E4%B8%80%E9%81%93LeetCode%E5%BC%95%E5%8F%91%E7%9A%84%E6%83%A8%E6%A1%88/">上一道困难题超时了</a></p>
<p>这题虽然说是困难题但是其实也不难，感觉就mid左右的水平，确实比上一题要复杂一点，但是只要思路理清楚其实也挺简单的，下面是我用OneNote画的一张图片。</p>
<p>4个指针分别对应 K 链表的 前一个(pre)  K链表的头节点(cur) 没有翻转前的K链表的头节点and<strong>翻转后的尾节点(temp)</strong>   K链表的后一个节点(next)。然后其实就简单了，写一个翻转链表的函数然后返回头节点(也可以多加一个指针指向<strong>翻转前的头节点</strong>)，然后就简单了，next指针一次走K步，走到 K+1 位置 同时也是<strong>下一次K链表的头节点</strong>，而temp则为下一次K链表的pre…然后循环这个过程就行了，其实写成递归会很简洁，但是我是真的不会写递归，太菜了Orz</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top///20190312/jl7moiy7PbjH.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>解法二</strong></p>
<p>2020.2.23 时隔多年现在回头重新写了一个递归的写法，还是比较简洁的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//时隔一年,回头自己写了一个递归的解法</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">reverseKGroup</span><span class="params">(ListNode head, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span> || k==<span class="number">1</span>) <span class="keyword">return</span> head;</span><br><span class="line">    <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">    ListNode temp=head;</span><br><span class="line">    <span class="comment">//预先计算链表的长度</span></span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">        sum++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> reverse(head,k,sum);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">reverse</span><span class="params">(ListNode head, <span class="keyword">int</span> k,<span class="keyword">int</span> remain)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(remain&lt;k) <span class="keyword">return</span> head; <span class="comment">//ramain不足k个return </span></span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>) <span class="keyword">return</span> head;</span><br><span class="line">    <span class="comment">//正常的翻转操作</span></span><br><span class="line">    ListNode cur=head,pre=<span class="keyword">null</span>,last=head;</span><br><span class="line">    <span class="keyword">int</span> count=k;</span><br><span class="line">    <span class="keyword">while</span>(count-- &gt;<span class="number">0</span>)&#123;</span><br><span class="line">        last=cur.next;</span><br><span class="line">        cur.next=pre;</span><br><span class="line">        pre=cur;</span><br><span class="line">        cur=last;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//下一次从last开始翻转,remain-k</span></span><br><span class="line">    head.next=reverse(last,k,remain-k);</span><br><span class="line">    <span class="keyword">return</span> pre;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>解法三</strong></p>
<p>这题递归明显是不太符合要求的，空间复杂度不是常数的，如果有要求还是要写下面的解法</p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">reverseKGroup</span><span class="params">(head *ListNode, k <span class="keyword">int</span>)</span> *<span class="title">ListNode</span></span> &#123;</span><br><span class="line">    dummyNode := &amp;ListNode&#123;</span><br><span class="line">        Next: head,</span><br><span class="line">        Val:  <span class="number">-1</span>,</span><br><span class="line">    &#125;</span><br><span class="line">    pre := dummyNode</span><br><span class="line">    cur := head</span><br><span class="line">    <span class="comment">//-1 | 1 2 3 4 5</span></span><br><span class="line">    <span class="keyword">for</span> cur != <span class="literal">nil</span> &#123;</span><br><span class="line">        <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; k<span class="number">-1</span> &amp;&amp; cur != <span class="literal">nil</span>; i++ &#123;</span><br><span class="line">            cur = cur.Next</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> cur == <span class="literal">nil</span> &#123; <span class="comment">//不足k个</span></span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">        next := cur.Next</span><br><span class="line">        cur.Next = <span class="literal">nil</span> </span><br><span class="line">        start := pre.Next</span><br><span class="line">        pre.Next = reverse(start)</span><br><span class="line">        start.Next = next</span><br><span class="line">        <span class="comment">//这里要注意pre=start</span></span><br><span class="line">        pre = start</span><br><span class="line">        cur = next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dummyNode.Next</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">reverse</span><span class="params">(head *ListNode)</span> *<span class="title">ListNode</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> pre *ListNode</span><br><span class="line">    <span class="keyword">var</span> cur = head</span><br><span class="line">    <span class="keyword">for</span> cur != <span class="literal">nil</span> &#123;</span><br><span class="line">        next := cur.Next</span><br><span class="line">        cur.Next = pre</span><br><span class="line">        pre = cur</span><br><span class="line">        cur = next</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pre</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>隔一段时间就会重新写一遍，写肯定写的出来，就是要想清楚，最好搞个case在上面，一边模拟一边写</p>
<blockquote>
<p>做链表的题就是得细心啊，容易把自己绕进去，上面的解法就是看了题解才写出来的</p>
</blockquote>
<h2 id="817-链表组件"><a href="#817-链表组件" class="headerlink" title="817. 链表组件"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/linked-list-components" >817. 链表组件<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个链表（链表结点包含一个整型值）的头结点 head。<br>同时给定列表 G，该列表是上述链表中整型值的一个子集。<br>返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">head: <span class="number">0</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span></span><br><span class="line">G = [<span class="number">0</span>, <span class="number">1</span>, <span class="number">3</span>]</span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">解释: </span><br><span class="line">链表中,<span class="number">0</span> 和 <span class="number">1</span> 是相连接的，且 G 中不包含 <span class="number">2</span>，所以 [<span class="number">0</span>, <span class="number">1</span>] 是 G 的一个组件，同理 [<span class="number">3</span>] 也是一个组件，故返回 <span class="number">2</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">head: <span class="number">0</span>-&gt;<span class="number">1</span>-&gt;<span class="number">2</span>-&gt;<span class="number">3</span>-&gt;<span class="number">4</span></span><br><span class="line">G = [<span class="number">0</span>, <span class="number">3</span>, <span class="number">1</span>, <span class="number">4</span>]</span><br><span class="line">输出: <span class="number">2</span></span><br><span class="line">解释: </span><br><span class="line">链表中，<span class="number">0</span> 和 <span class="number">1</span> 是相连接的，<span class="number">3</span> 和 <span class="number">4</span> 是相连接的，所以 [<span class="number">0</span>, <span class="number">1</span>] 和 [<span class="number">3</span>, <span class="number">4</span>] 是两个组件，故返回 <span class="number">2</span>。</span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<ul>
<li>如果 N 是给定链表 head 的长度，1 &lt;= N &lt;= 10000。</li>
<li>链表中每个结点的值所在范围为 [0, N - 1]。</li>
<li>1 &lt;= G.length &lt;= 10000</li>
<li>G 是链表中所有结点的值的一个子集.</li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numComponents</span><span class="params">(ListNode head, <span class="keyword">int</span>[] G)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head==<span class="keyword">null</span>||head.next==<span class="keyword">null</span>) <span class="keyword">return</span> head;</span><br><span class="line">    ListNode temp=head;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(isInG(temp.val,G))&#123;</span><br><span class="line">            <span class="keyword">while</span>(temp!=<span class="keyword">null</span>&amp;&amp;isInG(temp.val,G))&#123;</span><br><span class="line">                temp=temp.next;</span><br><span class="line">            &#125;</span><br><span class="line">            res++;</span><br><span class="line">            <span class="keyword">if</span>(temp==<span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span> res;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Boolean <span class="title">isInG</span><span class="params">(<span class="keyword">int</span> val,<span class="keyword">int</span>[] G)</span></span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(G[i]==val)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>首先想到的方法 91ms 19%….. 有点慢了，然后我稍微改了下。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numComponents2</span><span class="params">(ListNode head, <span class="keyword">int</span>[] G)</span> </span>&#123;</span><br><span class="line">    ListNode temp=head;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    Boolean [] isInG=<span class="keyword">new</span> Boolean[<span class="number">10000</span>];</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;G.length;i++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(G[i]==temp.val)&#123;</span><br><span class="line">                isInG[j]=<span class="keyword">true</span>;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        j++;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    temp=head;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;temp!=<span class="keyword">null</span>;temp=temp.next,i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(isInG[i])&#123;</span><br><span class="line">            <span class="keyword">while</span>(temp!=<span class="keyword">null</span>&amp;&amp;isInG[i])&#123;</span><br><span class="line">                temp=temp.next;</span><br><span class="line">                i++;</span><br><span class="line">            &#125;</span><br><span class="line">            res++;</span><br><span class="line">            <span class="keyword">if</span>(temp==<span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span> res;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>   用了一个数组保存了每个位置的状态速度跟前面的差不多。。。主要问题就是那个数组的创建，这种创建方式用连续的下标来对应连续的链表的每个元素，每次都要遍历G才知道当前位置是不是在G中。</p>
<p>   其实可以直接把当前节点的val作为数组的下标这样既有了对应关系也不用遍历G.可以说是很优秀了，但是实际上这样做是有前提条件的那就是链表中的元素值应该<code>没有负数</code>，还是题做少了啊 Orz。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numComponents3</span><span class="params">(ListNode head, <span class="keyword">int</span>[] G)</span> </span>&#123;</span><br><span class="line">    ListNode temp=head;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    Boolean [] isInG=<span class="keyword">new</span> Boolean[<span class="number">10000</span>];</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//换一种方式 以node.val作为数组的下标</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i:G)&#123;</span><br><span class="line">        isInG[i]=<span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(isInG[temp.val])&#123;</span><br><span class="line">            <span class="keyword">while</span>(temp!=<span class="keyword">null</span>&amp;&amp;isInG[temp.val])&#123;</span><br><span class="line">                temp=temp.next;</span><br><span class="line">            &#125;</span><br><span class="line">            res++;</span><br><span class="line">            <span class="keyword">if</span>(temp==<span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="keyword">return</span> res;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        temp = temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="1019-链表中的下一个更大节点"><a href="#1019-链表中的下一个更大节点" class="headerlink" title="1019. 链表中的下一个更大节点"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/next-greater-node-in-linked-list/" >1019. 链表中的下一个更大节点<i class="fas fa-external-link-alt"></i></a></h2><p>给出一个以头节点 <code>head</code> 作为第一个节点的链表。链表中的节点分别编号为：<code>node_1, node_2, node_3, ...</code> 。</p>
<p>每个节点都可能有下一个更大值（next larger <strong>value</strong>）：对于 <code>node_i</code>，如果其 <code>next_larger(node_i)</code> 是 <code>node_j.val</code>，那么就有 <code>j &gt; i</code> 且  <code>node_j.val &gt; node_i.val</code>，而 <code>j</code> 是可能的选项中最小的那个。如果不存在这样的 <code>j</code>，那么下一个更大值为 <code>0</code> 。</p>
<p>返回整数答案数组 <code>answer</code>，其中 <code>answer[i] = next_larger(node_&#123;i+1&#125;)</code> 。</p>
<p><strong>注意：</strong> 在下面的示例中，诸如 <code>[2,1,5]</code> 这样的<strong>输入</strong>（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">2</span>,<span class="number">1</span>,<span class="number">5</span>]</span><br><span class="line">输出：[<span class="number">5</span>,<span class="number">5</span>,<span class="number">0</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">2</span>,<span class="number">7</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">5</span>]</span><br><span class="line">输出：[<span class="number">7</span>,<span class="number">0</span>,<span class="number">5</span>,<span class="number">5</span>,<span class="number">0</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">1</span>,<span class="number">7</span>,<span class="number">5</span>,<span class="number">1</span>,<span class="number">9</span>,<span class="number">2</span>,<span class="number">5</span>,<span class="number">1</span>]</span><br><span class="line">输出：[<span class="number">7</span>,<span class="number">9</span>,<span class="number">9</span>,<span class="number">9</span>,<span class="number">0</span>,<span class="number">5</span>,<span class="number">0</span>,<span class="number">0</span>]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li>对于链表中的每个节点，<code>1 &lt;= node.val &lt;= 10^9</code></li>
<li>给定列表的长度在 <code>[0, 10000]</code> 范围内</li>
</ol>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] nextLargerNodes(ListNode head) &#123;</span><br><span class="line">    <span class="comment">//list里面存元素</span></span><br><span class="line">    ArrayList&lt;Integer&gt; A = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (ListNode node = head; node != <span class="keyword">null</span>; node = node.next)</span><br><span class="line">                A.add(node.val);</span><br><span class="line">    <span class="keyword">int</span>[] res = <span class="keyword">new</span> <span class="keyword">int</span>[A.size()];</span><br><span class="line">    <span class="comment">//栈里面存索引</span></span><br><span class="line">    Stack&lt;Integer&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; A.size(); ++i) &#123;</span><br><span class="line">        <span class="keyword">while</span> (!stack.isEmpty() &amp;&amp; A.get(stack.peek()) &lt; A.get(i))</span><br><span class="line">             res[stack.pop()] = A.get(i);</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>新题，磨了好长时间，没做出来。。。真是菜啊 Orz，70ms，因为跑两遍。下面这个<code>14ms</code>可以说是相当快了，但，时间可能耗费在建立栈和list上了，看了下提交上的前几个都是用的数组，用数组模拟的栈。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//和上面的方法差不多,但这个更快，上面那个跑了两遍</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] nextLargerNodes3(ListNode head) &#123;</span><br><span class="line">    <span class="keyword">int</span>[] stack = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">    <span class="keyword">int</span>[] res = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">    <span class="comment">//temp是链表的副本，相当于上面的list</span></span><br><span class="line">    <span class="keyword">int</span>[] temp = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">    <span class="comment">//top 栈顶</span></span><br><span class="line">    <span class="keyword">int</span> top = -<span class="number">1</span>, i = <span class="number">0</span>;</span><br><span class="line">    ListNode node = head;</span><br><span class="line">    <span class="keyword">while</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">while</span> (top != -<span class="number">1</span> &amp;&amp; temp[stack[top]] &lt; node.val)&#123;</span><br><span class="line">            <span class="comment">//后一个大于当前节点, 栈不为空</span></span><br><span class="line">            <span class="comment">//pop出比它小的元素并赋值res，重新生成单调栈</span></span><br><span class="line">            res[stack[top--]] = node.val;</span><br><span class="line">        &#125;</span><br><span class="line">        stack[++top] = i;</span><br><span class="line">        temp[i++] = node.val;</span><br><span class="line">        node = node.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Arrays.copyOf(res, i);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>思路就是利用<code>单调栈</code>，栈里面存的索引对应的元素都是单调递减的，遇到不递减的就会一直pop()直到再次单调递减。这样很容易就找到了每个元素的下一个最大元素了。</p>
<p>19.7.21 重新做了一遍这道题，第一遍还是没想出来，还是看了之前的代码</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] nextLargerNodes5(ListNode head) &#123;</span><br><span class="line">        List&lt;Integer&gt; list=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        ListNode temp=head;</span><br><span class="line">        <span class="keyword">while</span>(temp!=<span class="keyword">null</span>)&#123;</span><br><span class="line">            list.add(temp.val);</span><br><span class="line">            temp=temp.next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> [] stack=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">        <span class="keyword">int</span> stackIndex=-<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">int</span> [] res=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;list.size();i++) &#123;</span><br><span class="line">            <span class="keyword">while</span>(stackIndex!=-<span class="number">1</span> &amp;&amp; list.get(i)&gt;list.get(stack[stackIndex]))&#123;</span><br><span class="line">                res[stack[stackIndex--]]=list.get(i);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//维护一个递减的栈</span></span><br><span class="line">            stack[++stackIndex]=i;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>  Arrays.copyOf(res, list.size());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>相比上面的方法一，采用了数组模拟队列(数据范围已经给定了)，30ms，80% 。仔细看看代码发现其实第一个循环完全没有必要，可以一边遍历一边存进去。</p>
<p><strong>一次遍历</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] nextLargerNodes6(ListNode head) &#123;</span><br><span class="line">    List&lt;Integer&gt; list=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    ListNode temp=head;</span><br><span class="line">    <span class="keyword">int</span> [] stack=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">    <span class="keyword">int</span> stackIndex=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> [] res=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;temp!=<span class="keyword">null</span>;i++) &#123;</span><br><span class="line">        list.add(temp.val);</span><br><span class="line">        <span class="keyword">while</span>(stackIndex!=-<span class="number">1</span> &amp;&amp; list.get(i)&gt;list.get(stack[stackIndex]))&#123;</span><br><span class="line">            res[stack[stackIndex--]]=list.get(i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//维护一个递减的栈</span></span><br><span class="line">        stack[++stackIndex]=i;</span><br><span class="line">        temp=temp.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>  Arrays.copyOf(res, list.size());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>优化后发现比之前还慢了。。。</p>
<p><strong>数组模拟链表</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] nextLargerNodes7(ListNode head) &#123;</span><br><span class="line">       <span class="keyword">int</span> [] list=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">       ListNode temp=head;</span><br><span class="line">       <span class="keyword">int</span> [] stack=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line">       <span class="keyword">int</span> stackIndex=-<span class="number">1</span>;</span><br><span class="line">       <span class="keyword">int</span> [] res=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">10000</span>];</span><br><span class="line"></span><br><span class="line">       <span class="keyword">int</span> i;</span><br><span class="line">       <span class="keyword">for</span> ( i=<span class="number">0</span>;temp!=<span class="keyword">null</span>;i++) &#123;</span><br><span class="line">           list[i]=temp.val;</span><br><span class="line">           <span class="keyword">while</span>(stackIndex!=-<span class="number">1</span> &amp;&amp; list[i]&gt;list[stack[stackIndex]])&#123;</span><br><span class="line">               res[stack[stackIndex--]]=list[i];</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="comment">//维护一个递减的栈</span></span><br><span class="line">           stack[++stackIndex]=i;</span><br><span class="line">           temp=temp.next;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="keyword">return</span>  Arrays.copyOf(res, i);</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>

<p>这次提交了几次直接 8ms 100%了。。。</p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：LeetCode链表</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2019-02-27 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2019/02/27/bef97aa3/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2019/04/07/32b13d92/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Java多线程基础</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2018/12/11/83535e94/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">常见的排序算法总结</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2019/02/27/bef97aa3/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#2-%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0"><span class="nav-number">1.</span> <span class="nav-text">2. 两数相加</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#445-%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0%E2%85%A1"><span class="nav-number">2.</span> <span class="nav-text">445. 两数相加Ⅱ</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#876-%E9%93%BE%E8%A1%A8%E7%9A%84%E4%B8%AD%E9%97%B4%E8%8A%82%E7%82%B9"><span class="nav-number">3.</span> <span class="nav-text">876. 链表的中间节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#206-%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8"><span class="nav-number">4.</span> <span class="nav-text">206. 反转链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#92-%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8%E2%85%A1"><span class="nav-number">5.</span> <span class="nav-text">92. 反转链表Ⅱ</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#725-%E5%88%86%E9%9A%94%E9%93%BE%E8%A1%A8"><span class="nav-number">6.</span> <span class="nav-text">725. 分隔链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#86-%E5%88%86%E9%9A%94-%E5%89%B2-%E9%93%BE%E8%A1%A8"><span class="nav-number">7.</span> <span class="nav-text">86. 分隔(割)链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#160-%E7%9B%B8%E4%BA%A4%E9%93%BE%E8%A1%A8"><span class="nav-number">8.</span> <span class="nav-text">160. 相交链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#234-%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8"><span class="nav-number">9.</span> <span class="nav-text">234. 回文链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#237-%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9"><span class="nav-number">10.</span> <span class="nav-text">237. 删除链表中的节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#203-%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0"><span class="nav-number">11.</span> <span class="nav-text">203. 移除链表元素</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#19-%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9"><span class="nav-number">12.</span> <span class="nav-text">19. 删除链表的倒数第N个节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#82-%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0%E2%85%A1"><span class="nav-number">13.</span> <span class="nav-text">82. 删除排序链表中的重复元素Ⅱ</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#83-%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0"><span class="nav-number">14.</span> <span class="nav-text">83. 删除排序链表中的重复元素</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E9%A2%98-02-01-%E7%A7%BB%E9%99%A4%E9%87%8D%E5%A4%8D%E8%8A%82%E7%82%B9"><span class="nav-number">15.</span> <span class="nav-text">面试题 02.01. 移除重复节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#143-%E9%87%8D%E6%8E%92%E9%93%BE%E8%A1%A8"><span class="nav-number">16.</span> <span class="nav-text">143. 重排链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#21-%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8"><span class="nav-number">17.</span> <span class="nav-text">21. 合并两个有序链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#23-%E5%90%88%E5%B9%B6K%E4%B8%AA%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8"><span class="nav-number">18.</span> <span class="nav-text">23. 合并K个排序链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#355-%E8%AE%BE%E8%AE%A1%E6%8E%A8%E7%89%B9"><span class="nav-number">19.</span> <span class="nav-text">355. 设计推特</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#430-%E6%89%81%E5%B9%B3%E5%8C%96%E5%A4%9A%E7%BA%A7%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8"><span class="nav-number">20.</span> <span class="nav-text">430. 扁平化多级双向链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#141-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8"><span class="nav-number">21.</span> <span class="nav-text">141. 环形链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#141-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8%E2%85%A1"><span class="nav-number">22.</span> <span class="nav-text">141. 环形链表Ⅱ</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#61-%E6%97%8B%E8%BD%AC%E9%93%BE%E8%A1%A8"><span class="nav-number">23.</span> <span class="nav-text">61.旋转链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#328-%E5%A5%87%E5%81%B6%E9%93%BE%E8%A1%A8"><span class="nav-number">24.</span> <span class="nav-text">328. 奇偶链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#147-%E5%AF%B9%E9%93%BE%E8%A1%A8%E8%BF%9B%E8%A1%8C%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="nav-number">25.</span> <span class="nav-text">147. 对链表进行插入排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#148-%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8"><span class="nav-number">26.</span> <span class="nav-text">148. 排序链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#138-%E5%A4%8D%E5%88%B6%E5%B8%A6%E9%9A%8F%E6%9C%BA%E6%8C%87%E9%92%88%E7%9A%84%E9%93%BE%E8%A1%A8"><span class="nav-number">27.</span> <span class="nav-text">138.复制带随机指针的链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#24-%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9"><span class="nav-number">28.</span> <span class="nav-text">24. 两两交换链表中的节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#25-K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8"><span class="nav-number">29.</span> <span class="nav-text">25.K个一组翻转链表</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#817-%E9%93%BE%E8%A1%A8%E7%BB%84%E4%BB%B6"><span class="nav-number">30.</span> <span class="nav-text">817. 链表组件</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1019-%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E8%8A%82%E7%82%B9"><span class="nav-number">31.</span> <span class="nav-text">1019. 链表中的下一个更大节点</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
